首页 > 代码库 > 【BZOJ】 4813: [Cqoi2017]小Q的棋盘

【BZOJ】 4813: [Cqoi2017]小Q的棋盘

2024-09-15 23:53:23   216人阅读

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4813

暴力转移就好，考虑以某一个点为根的子树分为是否走回来两种情况

${f_{i,j}}$表示已点$i$为根的子树，走了$j$步之后回到点$i$最多能经过多少个点

${g_{i,j}}$表示已点$i$为根的子树，走了$j$步之后不管停在那个点最多能经过多少个点

 

写了个${n^{2}}$转移

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cmath> 6 #include<cstring> 7 #include<queue> 8 #include<vector> 9 #include<map>10 using namespace std;11 #define llg int12 #define maxn 21013 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);14 vector<llg>a[maxn];15 llg f[maxn][maxn],g[maxn][maxn],n,m;16 inline llg getint()17 {18     llg w=0,q=0; char c=getchar();19     while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar();20     if (c==‘-‘)  q=1, c=getchar(); while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar();21     return q ? -w : w;22 }23 24 void init()25 {26     cin>>n>>m;27     for (llg i=1;i<n;i++)28     {29         llg x=getint()+1,y=getint()+1;30         a[x].push_back(y),a[y].push_back(x);31     }32 }33 34 void dp(llg x,llg fa)35 {36     llg w=a[x].size(),v;37     f[x][0]=g[x][0]=1;38     for (llg e=0;e<w;e++)39     {40         v=a[x][e];41         if (v==fa) continue;42         dp(v,x);43         for (llg i=m;i>=1;i--)44         {45             for (llg j=0;j<i;j++)46             {47                 if (i-j>=2)48                 {49                     f[x][i]=max(f[x][i],f[v][j]+f[x][i-j-2]);50                     g[x][i]=max(g[x][i],f[v][j]+g[x][i-j-2]);51                 }52                 g[x][i]=max(g[x][i],g[v][j]+f[x][i-j-1]);53             }54         }55     }56     for (llg i=0;i<m;i++) f[x][i+1]=max(f[x][i+1],f[x][i]),g[x][i+1]=max(g[x][i+1],g[x][i]);57 }58 59 int main()60 {61     yyj("dp");62     init();63     dp(1,0);64     cout<<g[1][m];65     return 0;66 }

 

【BZOJ】 4813: [Cqoi2017]小Q的棋盘


联系
我们