huangjingling @ 2020-02-06 18:25:02
#include<stdio.h>
int max(int a,int b){return (a>b)?a:b;}
int main()
{
int dp[32010]={0};
int v[65][3]={0},w[65][3]={0};
int n,m,count=0;
scanf("%d %d",&n,&m);
for(int i=0,j=0,k=1;j<m;j++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
if(z==0){i++;v[i][0]=x;w[i][0]=y;count++;}
else if(z!=0){k=1;if(w[z][k]!=0)k=2;v[z][k]=x;w[z][k]=y;}
}
for(int i=1;i<=count;i++)
for(int j=n;j>=0;j--)
{
if(j>=v[i][0])dp[j]=max(dp[j],dp[j-v[i][0]]+w[i][0]*v[i][0]);
if((j>=(v[i][0]+v[i][1]))&&w[i][1]!=0)dp[j]=max(dp[j],dp[j-v[i][0]-v[i][1]]+v[i][0]*w[i][0]+v[i][1]*w[i][1]);
if((j>=(v[i][0]+v[i][2]))&&w[i][2]!=0)dp[j]=max(dp[j],dp[j-v[i][0]-v[i][2]]+v[i][0]*w[i][0]+v[i][2]*w[i][2]);
if((j>=(v[i][0]+v[i][1]+v[i][2]))&&w[i][1]!=0&&w[i][2]!=0)dp[j]=max(dp[j],dp[j-v[i][0]-v[i][2]-v[i][1]]+v[i][0]*w[i][0]+v[i][1]*w[i][1]+v[i][2]*w[i][2]);
//printf("dp[%d]=%d\n",j,dp[j]);
}
printf("%d",dp[n]);
}
by TonyWu @ 2020-02-18 20:34:22
@huangjingling 这。。。码风我不太习惯。能不能解释一下。
by TonyWu @ 2020-02-18 20:36:04
@huangjingling 我第一次60是因为没有把给的q转换为真正的第q行。
Input
2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5
Output
7430
by huangjingling @ 2020-02-21 16:05:07
@TonyWu 对,就是这个问题,读题不清