1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
|
#include <cstdio> #include <cstdlib>
using namespace std; const int maxn=1010; int n,m; int dp[maxn],a[maxn],b[maxn],c[105][1010],p[105],cnt,opt; int () { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&a[i],&b[i],&opt); cnt=max(cnt,opt); c[opt][++p[opt]]=i; } for(int i=1;i<=cnt;i++) { for(int j=m;j>=0;j--) { for(int k=1;k<=p[i];k++) { if(j>=a[c[i][k]]) dp[j]=max(dp[j],dp[j-a[c[i][k]]]+b[c[i][k]]); } } } printf("%dn",dp[m]); return 0; }
|
近期评论