WA 树形dp代码求调

P2016 战略游戏

nyC20 @ 2024-05-28 20:16:25

#include <bits/stdc++.h>
using namespace std;
int n,v[1750],en[1750],h[1750],ne[1750],f[1750][13],cnt;
bool mark[1750];
void add(int a,int b)
{
    en[++cnt]=b;
    ne[cnt]=h[a];
    h[a]=cnt;
    return;
}
void dp(int x)
{
    f[x][1]=v[x];
    int minn=INT_MAX;
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int y=en[i];
        dp(y);
        f[x][0]+=min(f[y][1],f[y][2]);
        f[x][1]+=min(f[y][0],min(f[y][1],f[y][2]));
        f[x][2]+=min(f[y][1],f[y][2]);
        minn=min(minn,f[y][1]-min(f[y][1],f[y][2]));
    }
    f[x][2]+=minn;
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,z,sl;
        cin>>x>>sl;
        v[x]=1;
        for(int j=1;j<=sl;j++)
        {
            int y;
            cin>>y;
            mark[y]=true;
            add(x,y);
        }
    }
    int t;
    for(int i=1;i<=n;i++)
    {
        if(mark[i]==false)
        {
            t=i;
            break;
        }
    }
    dp(t);
    cout<<min(f[t][1],f[t][2])<<endl;
    return 0;
}

提交记录


by Addicted_Game @ 2024-05-28 20:47:22

一眼就知道你是复制的以前的代码

这两道题不一样


by ___nyLittleT___ @ 2024-05-28 20:56:34

@Addicted_Game @nyC20 Vegetables need more exercise.


by nyC20 @ 2024-05-28 21:00:46

@Addicted_Game 被看出来力


|