E-清楚姐姐的布告规划【01背包】

就当一个01背包写就行，只不过需要保证不交叉，w[i]覆盖i点，用一个if来判断即可

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int w[5005];
int f[5005];
int t,n,m;
signed main()
{cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++)cin>>w[i],f[i]=1e9;//初始化f[0]=0;//一开始肯定是0初始化for(int i=1;i<=n;i++){for(int j=n;j>=w[i];j--)//01背包j表示放了之后的面积{if(j>=i&&j-w[i]<i)//这里不能j-w[i]<=i,=i会重合{f[j]=min(f[j],f[j-w[i]]+1);}}}if(f[n]==1e9) cout<<-1<<endl;else cout<<f[n]<<endl;}return 0;
}