charm bracelet
01背包,用二维做MLE了。。。
模板题。。。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define max(a,b) a>b?a:b int const M = 3500; int w[M],d[M],val[M * 4]; int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ for(int i = 1;i <= n;i++){ scanf("%d%d",&w[i],&d[i]); } memset(val,0,sizeof(val)); for(int i = 1;i <= n;i++){ for(int j = m;j >= 0;j--) if(j >= w[i])val[j] = max(val[j],val[j - w[i]] + d[i]); } printf("%d\n",val[m]); } return 0; }