http://acm.hdu.edu.cn/showproblem.php?pid=2159
一开始想的是三维的dp,没注意到是可以重复取的,卡了一下。最终1A,虽然ac了,但是我还是对这个结果不太满意
太慢了!!!105ms,6M多内存。。。恩,可以优化
想了大半天,就想到了个奇偶节省内存的,还是看下大连理工大神的代码
吓死我了,o(n)的内存,n^2的复杂度
原来最后的一层循环对选择个数的限制是没有必要的
原因是:对于dp【i】【m】来说,这样的忍耐度,打小怪的个数肯定是越小越优的,不会出现其他更优的情况,所以只要保存最小的那个就可以了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> using namespace std; const int MAXN=100; int dp[MAXN],cnt[MAXN]; int w[MAXN],v[MAXN]; int main() { // freopen("in","r",stdin); int n,m,k,s; HH: while(~scanf("%d %d %d %d",&n,&m,&k,&s)) { for(int i=0; i<k; i++) scanf("%d%d",v+i,w+i); memset(dp,0,sizeof(dp)); memset(cnt,0,sizeof(cnt)); for(int i=0; i<k; i++) for(int j=w[i];j<=m;j++) if(dp[j]<dp[j-w[i]]+v[i]) dp[j]=dp[j-w[i]]+v[i],cnt[j]=cnt[j-w[i]]+1; for(int i=0;i<=m;i++) { if(cnt[i]<=s && dp[i]>=n) { cout<<m-i<<endl; goto HH; } } cout<<-1<<endl; } return 0; }