monkey123456 @ 2022-08-21 15:31:48
#include<stdio.h>
int dp[35005];
int max(int a,int b)、
{
if(a<b) return b;
return a;
}
int flag[35005];
int main()
{
int T,num,n[1005],v[1005];//钱 n个数 钱 重要
int q[1005];//配件
scanf("%d%d",&T,&num);
for(int i=1;i<=num;i++) scanf("%d%d%d",&n[i],&v[i],&q[i]);
for(int i=1;i<=num;i++)
{
for(int j=T;j>=0;j--)
{
if(q[i]==0) // 主件
{
if(j>=n[i]) dp[j]=max(dp[j],dp[j-n[i]]+n[i]*v[i]);
flag[i]=114514;
}
else // 配件
{
if(flag[q[i]]==114514)// 买过主件
{
if(j>=n[i]) dp[j]=max(dp[j],dp[j-n[i]]+n[i]*v[i]);
}
else if( flag[q[i]]!=114514 ) // 没买主件
{
if(j>=(n[q[i]]+n[i]))
{
dp[j]=max(dp[j],dp[j-n[q[i]]-n[i]]+n[i]*v[i]+n[q[i]]*v[q[i]]);
flag[q[i]]=114514;
}
}
}
}
}
printf("%d",dp[T]);
return 0;
}
by monkey123456 @ 2022-09-06 12:41:46
@Programmerdcr 你还是不是人啦!
by Programmerdcr @ 2022-09-12 13:43:36
@monkey123456 你是不是香精鉴于,菊爆了