水题大法好!
有几天没写blog了呢。因为这几天颓废了。
#include<cstdio> #include<algorithm> using namespace std; int n,m,w[3500],c[3500],f[25000]; int main(){ freopen("1625.in","r",stdin); freopen("1625.out","w",stdout); scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d %d",&w[i],&c[i]); } for(int i=1;i<=n;i++){ for(int j=m;j>=w[i];j--){ f[j]=max(f[j],f[j-w[i]]+c[i]); } } printf("%d\n",f[m]); return 0; }