树形DP10分求助大佬

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

nia可真行 @ 2019-11-27 20:03:00

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,ans;
int mo[205],c[205],w[205],head[205],f[205][32005];
struct cxk{
    int nxt,to;
}e[32005];
int add(int x,int y)
{
    //cnt++;
    e[cnt].nxt=head[x];
    e[cnt].to=y;
    head[x]=cnt++;
}
void dfs(int u,int t)
{
    if(t<=0)
    return ;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==u)
        continue;
        for(int k=0;k<n-mo[v];k++)
        f[v][k]=f[u][k]+c[v];
        dfs(v,t-mo[v]);
        for(int k=mo[v];k<=n;k++)
        f[u][k]=max(f[u][k],f[v][k-mo[v]]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a;
        cin>>mo[i]>>w[i]>>a;
        c[i]=mo[i]*w[i];
        add(a,i);
        //add(i,a);
    }
    memset(f,0,sizeof(f));
    //memset(head,-1,sizeof(head));
    dfs(0,n);
    for(int i=0;i<n;i++)
    ans=max(ans,f[0][i]);
    cout<<ans;
    return 0;
}

by libear @ 2019-11-27 20:38:48

这道题难道不是背包么???


by Crab_Dave @ 2019-12-20 22:16:46

for(int k=0;k<n-mo[v];k++)
          f[v][k]=f[u][k]+c[v];
dfs(v,t-mo[v]);
for(int k=mo[v];k<=n;k++)
          f[u][k]=max(f[u][k],f[v][k-mo[v]]);

这个地方不对,应该从 n-mo[v]k 才对。

因为每个物品只能选一次,如果让 k 递增的话,之前可能会有一种情况,选了该物品更优;然后 k 变为 k+mo[v] 时,如果仍然优秀,就会再选择一次。

不知道讲懂了么qwq


by Crab_Dave @ 2019-12-21 11:50:20

而且最后统计答案时应该从0到n而不是n-1,因为可以刚好把钱花完。


by Crab_Dave @ 2019-12-21 11:57:11

应该没有问题了qwq


by TonyWu @ 2020-02-18 21:01:44

@nia可真行 树形DP。。。tql%%%


|