P1064 [NOIP2006 提高组] 金明的预算方案 题解
P1064 [NOIP2006 提高组] 金明的预算方案
//P1064 [NOIP2006 提高组] 金明的预算方案
//因为附件最多2个，所以对于每个主件只有以下四种情况：
//1.不选主件 2.只选主件 3.选第一个附件 4.选第二个附件 5.选两个附件
//几乎就是01背包的板子了
//每次更新注意可以选该物品的条件即可
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=210;
int dp[N][50010];//买前i种主件花j元的结果
int n,m,v[N],p[N],q[N];
int son[N][2];
int main()
{
memset(son,-1,sizeof son);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&v[i],&p[i],&q[i]);
if(q[i]!=0) son[q[i]][son[q[i]][0]==-1?0:1]=i;//依赖于主件q[i]的2个附件
}
int la=0;//易错！用前一个主件的dp值更新的时候不能直接用i-1，因为上一个可能是附件，dp值没有意义（没有单独存主件的弊端）
for(int i=1;i<=m;i++)
{
if(q[i]) continue;
for(int j=1;j<=n;j++)
{
if(v[i]>j) dp[i][j]=dp[la][j];
else
{
dp[i][j]=max(dp[la][j],dp[la][j-v[i]]+v[i]*p[i]);
if(son[i][0]!=-1&&v[i]+v[son[i][0]]<=j)
dp[i][j]=max(dp[i][j],dp[la][j-v[i]-v[son[i][0]]]+v[son[i][0]]*p[son[i][0]]+v[i]*p[i]);
if(son[i][1]!=-1&&v[i]+v[son[i][1]]<=j)
dp[i][j]=max(dp[i][j],dp[la][j-v[i]-v[son[i][1]]]+v[son[i][1]]*p[son[i][1]]+v[i]*p[i]);
if(son[i][0]!=-1&&son[i][1]!=-1&&v[i]+v[son[i][0]]+v[son[i][1]]<=j)
dp[i][j]=max(dp[i][j],dp[la][j-v[i]-v[son[i][0]]-v[son[i][1]]]+v[son[i][0]]*p[son[i][0]]+v[son[i][1]]*p[son[i][1]]+v[i]*p[i]);
}
}
la=i;
//printf("dp[%d]=%d\n",i,dp[la][n]);
}
printf("%d",dp[la][n]);//易错！同上面的错误一样，不能直接用第m个的dp值，因为可能是附件，直接用la记录的最后一个主件即可
return 0;
}