【简单DP】代码源每日一题div2 树

Dear 丶 2024-03-16 16:49 18阅读 0赞

[树 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![a4d4c61e3adb48be8214c3e6f5bbda1a.png][]

思路：

一开始很自然的去想树形DP

![68f1383025f94e08bc2d648c8fae7a93.jpeg][]

后来发现，根本不能转移呀

然后就不会了

事实上是个背包题

每操作一个结点都会产生Out\[u\]的贡献，Out\[u\]表示结点u的出度，然后问你贡献为K的最小操作次数

跑背包即可

请问这是怎么想到的呢？我也不知道，大概手摸样例就能发现性质了（？

![aae5071b5f94614fca74631b07df13dd.jpeg][]

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=3e3+10;
    const int mxe=3e3+10;
    const int Inf=0x3f3f3f3f;
    
    int N,Fa;
    int a[mxn];
    int Out[mxn],dp[mxn][mxn];
    
    void solve(){
        cin>>N;
        for(int i=2;i<=N;i++){
            cin>>Fa;
            Out[Fa]++;
        }
        memset(dp,0x3f,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=N;i++){
            for(int j=0;j<=N;j++){
                dp[i][j]=min(dp[i][j],dp[i-1][j]);
                if(j>=Out[i]) dp[i][j]=min(dp[i][j],dp[i-1][j-Out[i]]+1);
            }
        }
        for(int j=1;j<=N;j++){
            if(dp[N][j-1]==Inf) cout<<-1<<" \n"[j==N];
            else cout<<dp[N][j-1]<<" \n"[j==N];
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/154
[a4d4c61e3adb48be8214c3e6f5bbda1a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/ef57a31199cc48f183c0d774b49f7b17.png
[68f1383025f94e08bc2d648c8fae7a93.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/6430903401fd491580a4b9bd775dc68b.png
[aae5071b5f94614fca74631b07df13dd.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/a52ab2a85558482089074de6225c77e6.png