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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
|
using namespace std; typedef long long ll; const int maxn = 40000; int n,m; int v,p,q; int c[65][4]; int w[65][4]; int dp[2][maxn]; int pre=0,now=1; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&v,&p,&q); if(q==0){ c[i][0]++; c[i][1]=v; w[i][1]=p*v; } else{ c[q][0]++; if(c[q][2]){ c[q][3]=v; w[q][3]=p*v; } else{ c[q][2]=v; w[q][2]=p*v; } } } for(int i=1;i<=m;i++){ if(c[i][0]==0)continue; if(c[i][0]>=1){ for(int j=n;j>=1;j--){ dp[now][j]=max(dp[now][j],dp[pre][j]); if(j-c[i][1]>=0){ dp[now][j]=max(dp[now][j],dp[pre][j-c[i][1]] + w[i][1]); } } } if(c[i][0]>=2){ for(int j=n;j>=1;j--){ dp[now][j]=max(dp[now][j],dp[pre][j]); if(j-c[i][1]-c[i][2]>=0){ dp[now][j]=max(dp[now][j],dp[pre][j-c[i][1]-c[i][2]] + w[i][1]+w[i][2]); } } } if(c[i][0]==3){ for(int j=n;j>=1;j--){ dp[now][j]=max(dp[now][j],dp[pre][j]); if(j-c[i][1]-c[i][3]>=0){ dp[now][j]=max(dp[now][j],dp[pre][j-c[i][1]-c[i][3]] + w[i][1]+w[i][3]); } if(j-c[i][1]-c[i][2]-c[i][3]>=0){ dp[now][j]=max(dp[now][j],dp[pre][j-c[i][1]-c[i][2]-c[i][3]] + w[i][1]+w[i][2]+w[i][3]); } } } now^=1;pre^=1; } int ans=0; for(int i=0;i<=n;i++)ans=max(ans,dp[pre][i]); cout<<ans; return 0; }
|
近期评论