BZOJ 1813 [Cqoi2017]小Q的棋盘 ——树形DP

ゞ浴缸里的玫瑰 2021-09-20 13:26 258阅读 0赞

唔，貌似以前做过这样差不多的题目。

用$f(i,0/1)$表示从某一点出发，只能走子树的情况下回到根、不回到根的最多经过不同的点数。

然后就可以DP辣

#include <map>
    #include <cmath>
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define F(i,j,k) for (int i=j;i<=k;++i)
    #define D(i,j,k) for (int i=j;i>=k;--i)
    #define ll long long
    #define mp make_pair
     
    int dp[105][105][2],n,m;
    int h[205],to[205],ne[205],en=0;
     
    void add(int a,int b)
    {to[en]=b;ne[en]=h[a];h[a]=en++;}
     
    void Finout()
    {
        freopen("chessboard.in","r",stdin);
        freopen("chessboard.out","w",stdout);
    }
     
    void dfs(int o,int fa)
    {
        dp[o][0][1]=1;
        for (int i=h[o];i>=0;i=ne[i])
            if (to[i]!=fa)
            {
                dfs(to[i],o);
                for (int j=m;j>=0;--j)
                {
                    for (int k=0;k<=j-2;++k)
                        dp[o][j][1]=max(dp[o][j][1],dp[to[i]][k][1]+dp[o][j-k-2][1]);
                    for (int k=0;k<=j-2;++k)
                        dp[o][j][0]=max(dp[o][j][0],dp[to[i]][k][1]+dp[o][j-k-2][0]);
                    for (int k=0;k<=j-1;++k)
                        dp[o][j][0]=max(dp[o][j][0],dp[to[i]][k][0]+dp[o][j-k-1][1]);
                }
            }
        for (int j=m;j>=0;--j)
            dp[o][j][0]=max(dp[o][j][0],dp[o][j][1]);
    }
     
    int main()
    {
        memset(dp,-0x3f,sizeof dp);
        memset(h,-1,sizeof h);
        scanf("%d%d",&n,&m);
        F(i,1,n-1)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            a++;b++;add(a,b);add(b,a);
        }
        dfs(1,-1);
        int ans=-1;
        F(i,0,m) ans=max(ans,max(dp[1][i][0],dp[1][i][1]));
        printf("%d\n",ans);
    }

转载于:https://www.cnblogs.com/SfailSth/p/6736852.html