比如样例的
800 2 0
400 5 1
300 5 1
而不能这样输入
400 5 1
800 2 0
300 5 1
或者别的,但是此法成功AC,算是巧了,巧了人家给的例子输入都按这种格式
#include<stdio.h>
#define max(a,b) (a>b?a:b)
int main()//由题知道最多两个附件
{
int n,m,i,j,k;
int k1=0,k2=0;
int t1=0,t2=0;
int v[200]={0},p[200]={0},q[200]={0},dp[32005]={0};
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&v[i],&p[i],&q[i]);
}
for(i=1;i<=m;i++)
{
k1=0;
k2=0;
t1=0;
t2=0;
if(q[i]==0)//确定主件
{
for(k=i+1;k<=m;k++)//找到附件1
{
if(q[k]==i)
{
t1=k;
k1=1;
break;
}
}
for(k=t1+1;k<=m;k++)//找到附件2
{
if(q[k]==i)
{
t2=k;
k2=1;
break;
}
}
for (j = n; j >= v[i]; j--) //遍历找出价值最大
{
dp[j] = max(dp[j - v[i]] + v[i] * p[i], dp[j]);//放主
//如果存在附件,比较放不放附件的价值
if (j-v[i]-v[t1]>=0 && k1==1)//放附1
dp[j] = max(dp[j - v[i]-v[t1]] + v[i] * p[i]+v[t1]*p[t1],dp[j]);
if (j - v[i] - v[t2] >= 0 && k2 == 1)//放附2
dp[j] = max(dp[j - v[i] - v[t2]] + v[i] * p[i] + v[t2] * p[t2], dp[j]);
if (j - v[i] - v[t1] - v[t2] >= 0 && k1 == 1 && k2 == 1)//都放
dp[j] = max(dp[j - v[i] - v[t1]-v[t2]] + v[i] * p[i] + v[t1] * p[t1] + v[t2] * p[t2], dp[j]);
}
}
}
printf("%d",dp[n]);
return 0;
}