456laji @ 2020-09-10 23:52:53
码风不好,请大佬们见谅。
#include<bits/stdc++.h>
using namespace std;
const int N=3200+100;
struct node
{
int price;
int degree;
}w[N];
int n,m,dp[N],num[N][N],vis[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int p=0;
scanf("%d%d%d",&w[i].price,&w[i].degree,&p);
if(p!=i&&p!=0)
vis[i]=1,num[p][0]++,num[p][num[p][0]]=i;
}
//for(int i=1;i<=m;i++)
// printf("%d %d \n",num[i][1],num[i][2]);
for(int i=1;i<=m;i++)
{
if(vis[i]) continue;
for(int j=n;j>=w[i].price;j--)
{
dp[j]=max(dp[j],dp[j-w[i].price]+w[i].price*w[i].degree);
if(num[i][0]==1)
{
int a=num[i][1];
if(j>=w[i].price+w[a].price)
dp[j]=max(dp[j],dp[j-w[i].price-w[a].price]+(w[i].degree*w[i].price)+(w[a].degree*w[a].price));
}
if(num[i][0]==2)
{
int a=num[i][1],b=num[i][2];
if(j>=w[i].price+w[a].price)
dp[j]=max(dp[j],dp[j-w[i].price-w[a].price]+(w[i].degree*w[i].price)+(w[a].degree*w[a].price));
if(j>=w[i].price+w[b].price)
dp[j]=max(dp[j],dp[j-w[i].price-w[b].price]+(w[i].degree*w[i].price)+(w[b].degree*w[b].price));
if(j>=w[i].price+w[a].price+w[b].price)
dp[j]=max(dp[j],dp[j-w[i].price-w[a].price-w[b].price]+(w[i].degree*w[i].price)+(w[a].degree*w[a].price)+(w[b].degree*w[b].price));
}
}
}
printf("%d\n",dp[n]);
return 0;
}
by Flora_Wisker @ 2020-10-03 09:04:04
不知道呢,好像没错