求助救命啊,60分求大家帮忙

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

衣香鬓影 @ 2018-09-29 09:50:33

我的想法是直接把附件挂在主件下面,用了vecto<int> a[61],然后根据每个a[i]数组大小判断有几个附件. 代码如下:

#include<iostream>
#include<vector>
using namespace std;

struct wupin
{
    int v;
    int p;
    int q;
};

vector<wupin> a[61];
long long dp[32005];

int max(int x,int y)
{
    return x>y?x:y;
}

int main()
{
    int money;
    int n;
    int zhu=0;
    cin>>money>>n;
    for(int i=1;i<=n;i++)
    {
        wupin x;
        cin>>x.v>>x.p>>x.q;
        if(x.q>0)  a[x.q].push_back(x);

        if(x.q==0)
        {
            zhu++;
            if(!a[zhu].empty())
            {
                a[zhu].push_back(a[zhu][0]);
                a[zhu][0]=x;
            }
            else a[zhu].push_back(x);   
        }
    }

    for(int i=1;i<=zhu;i++)
    {
        wupin now=a[i][0];
        for(int j=money;j>=now.v;j--)
        {
            dp[j]=max(dp[j],dp[j-now.v]+now.v*now.p);

            if(a[i].size()>=2)
              if(j>=now.v+a[i][1].v) 
                 dp[j]=max(dp[j],dp[j-now.v-a[i][1].v]+now.v*now.p+a[i][1].v*a[i][1].p);

            if(a[i].size()>=3)
            {
               if(j>=now.v+a[i][2].v) 
                  dp[j]=max(dp[j],dp[j-now.v-a[i][2].v]+now.v*now.p+a[i][2].v*a[i][2].p); 
               if(j>=now.v+a[i][1].v+a[i][2].v) 
                  dp[j]=max(dp[j],dp[j-now.v-a[i][1].v-a[i][2].v]+now.v*now.p+a[i][1].v*a[i][1].p+a[i][2].v*a[i][2].p);
            }
        }
    }

    cout<<dp[money]<<endl;
}

第三个点总是过不了:

2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5

题解答案:7430
我的答案:7200

想破脑袋也没想出来哪里有错。。。 请各位帮帮忙,谢谢大家了


|