求助!20分后8个点全WA

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

赤霞QvQ @ 2019-06-23 15:04:32

程序:

#include<bits/stdc++.h>
using namespace std;
int n,m,v,p,q,zhuv[65],zhuw[65],fuv[65][3],fuw[65][3],dp[32005];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v>>p>>q;
        if(q==0)
        {
            zhuv[i]=v;
            zhuw[i]=v*p;
        }
        else
        {
            fuv[i][0]++;
            fuv[i][fuv[i][0]]=v;
            fuw[i][fuv[i][0]]=v*p;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(zhuv[i]!=0)
        {
            for(int j=n;j>=zhuv[i];j--)
            {
                dp[j]=max(dp[j],dp[j-zhuv[i]]+zhuw[i]);
                if(j>=zhuv[i]+fuv[i][1])
                {
                    dp[j]=max(dp[j],dp[j-zhuv[i]-fuv[i][1]]+zhuw[i]+fuw[i][1]);
                }
                if(j>=zhuv[i]+fuv[i][2])
                {
                    dp[j]=max(dp[j],dp[j-zhuv[i]-fuv[i][2]]+zhuw[i]+fuw[i][2]);
                }
                if(j>=zhuv[i]+fuv[i][1]+fuv[i][2])
                {
                    dp[j]=max(dp[j],dp[j-zhuv[i]-fuv[i][1]-fuv[i][2]]+zhuw[i]+fuw[i][1]+fuw[i][2]);
                }
            }
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

真心查不出错哪了?


by 时间圣使·凡 @ 2019-06-23 16:08:46

\mathfrak{\color{red}\boxed{\color{yellow}\colorbox{blue}{请问哪题?}}}

by WatchmanIce @ 2019-06-23 19:45:26

@无赖学哥 蒟蒻来看看


by WatchmanIce @ 2019-06-23 19:47:15

@无赖学哥 这题树形dp啊蒟蒻开始瞎bb


by 赤霞QvQ @ 2019-06-23 21:37:40

@最帅的帅哥 P1064


by 赤霞QvQ @ 2019-06-23 21:37:52

@David崔 ????


by WatchmanIce @ 2019-06-25 19:54:35

@无赖学哥 应该是树形dp


by WatchmanIce @ 2019-06-25 19:54:55

@David崔 他们的关系网构成了一棵树


|