BZOJ4813: [Cqoi2017]小Q的棋盘

BZOJ4813

这么和善的树形dp。。我TM都要借助题解完成！！考个p的省选啊。。 很容易想到用两个状态 f[i][j],g[i][j] 分别表示从点 i 开始往下走j步且不用回到点 i 的方案/回到点i的方案。 。。然后我把转移想的贼复杂。。其实很容易的。。 就这样想，当前子节点可能对父节点有什么影响，可能从这个点走出去不回来，也可能从这个点走出又回到父节点。然后分别会对父节点两个状态有什么影响，就结了。 f[x][j]=max(f[x][j],f[v][k−1]+g[x][j−k]); g[x][j]=max(g[x][j],g[v][k−2]+g[x][j−k]); f[x][j]=max(f[x][j],g[v][k−2]+f[x][j−k]);

注意这个 j <script type="math/tex" id="MathJax-Element-377">j</script>要从大到小枚举，类似于背包。然后仔细看看式子就明白了。。

（后天省选。。做好AFO准备）

【代码】

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <stack> #include <cstring> #include <vector> #include <queue> #define N 105 #define M 8000005 #define mod 10000007 #define INF 1000000007 using namespace std; typedef long long ll; typedef pair<int,int> pa; ll read() { ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int n,m,cnt,sum,root; int b[N<<1],p[N],nextedge[N<<1],w[N<<1]; int f[N][N],g[N][N],dp[N]; void Add(int x,int y) { cnt++; b[cnt]=y; nextedge[cnt]=p[x]; p[x]=cnt; } void Anode(int x,int y){ Add(x,y);Add(y,x); } void Dfs(int x,int fa) { for(int i=0;i<=m;i++) g[x][i]=f[x][i]=1; for(int i=p[x];i;i=nextedge[i]) { int v=b[i];if(v==fa) continue; Dfs(v,x); for(int j=m;j;j--) { for(int k=1;k<=j;k++) { f[x][j]=max(f[x][j],f[v][k-1]+g[x][j-k]); if(k>=2) { g[x][j]=max(g[x][j],g[v][k-2]+g[x][j-k]); f[x][j]=max(f[x][j],g[v][k-2]+f[x][j-k]); } } } } } int main() { n=read(),m=read(); for(int i=1;i<n;i++) { static int x,y; x=read()+1,y=read()+1; Anode(x,y); } Dfs(1,0); printf("%d\n",f[1][m]); return 0; }