大神,求帮忙。

P1064 [NOIP2006 提高组] 金明的预算方案

lihaonan @ 2017-07-27 21:26:19

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxx=40001;
int n,m,dp[3][maxx],w[66],v[66];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int bj,x,y;
     scanf("%d%d%d",&x,&y,&bj);
    if(bj==0)
    {v[i]=x*y;
     w[i]=x;}
     else
     {v[bj]=v[i]*w[i]+v[bj]*w[bj];w[bj]+=w[i];
     v[i]=0;w[i]=0;}}
     for(int i=1;i<=m;i++)
      for(int j=n;j>=w[i];j--)
      {
       if(j>=w[i])
        dp[i%2][j]=max(dp[1-i%2][j],dp[1-i%2][j-w[i]]+v[i]);
        else
        dp[i%2][j]=dp[1-i%2][j];
        } 
        printf("%d",dp[m%2][n]);
        return 0;
}

|