题解 P3262 【[JLOI2015]战争调度】

· · 题解

的确是一道树形DP的好题目

题意简述：对于一颗完全二叉树，可以将叶子节点设置为两种状态（简称为0和1），如果该叶子节点与其某个祖先的状态相同，那么就有一个贡献值，两者都为0或1时对应两种不同的贡献值，求设置某种状态小于m时的最大贡献

由于这是一颗完全二叉树，那么其实就是分别求左右两个树形背包然后合并的结果

设 f[i][j] 表示以i为根的子树中，j个叶子节点选择战争的最大总贡献值。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();}
    return flag?-x:x;
}
int n,m;
int gh[1030][15],pt[1030][15],f[1030][1030],vis[15];
void dfs(int x,int y) //x表示节点，y表示层数
{
    for(int i=0;i<=1<<y;i++) f[x][i]=0;//全部初始化
    if(!y) //如果已经完成搜索（dp）
    {
    for(int i=1;i<=n;i++) 
      if(vis[i]) f[x][1]+=gh[x][i]; 
      else f[x][0]+=pt[x][i];return;
      //把贡献分别上交，退出
    }
    vis[y]=0,dfs(x<<1,y-1),dfs(x<<1|1,y-1);//分别去子节点
    for(int i=0;i<=1<<(y-1);i++) 
      for(int j=0;j<=1<<(y-1);j++) 
        f[x][i+j]=max(f[x][i+j],f[x<<1][i]+f[x<<1|1][j]);
    vis[y]=1,dfs(x<<1,y-1),dfs(x<<1|1,y-1);
    for(int i=0;i<=1<<(y-1);i++) 
      for(int j=0;j<=1<<(y-1);j++)
        f[x][i+j]=max(f[x][i+j],f[x<<1][i]+f[x<<1|1][j]);
    //在分别完成子树的搜索之后进行子树的合并
}
int main()
{
    int ans=0;
    n=read(),m=read(),n--;//不能超过n所以这里直接进行--处理
    for(int i=0;i<(1<<n);++i) 
      for(int j=1;j<=n;++j) 
        gh[i+(1<<n)][j]=read();//这个是存打仗的贡献，（givehead）
    for(int i=0;i<(1<<n);++i) 
      for(int j=1;j<=n;++j) 
        pt[i+(1<<n)][j]=read();//这个是存种地的贡献，（刨土）
    dfs(1,n);
    for(int i=0;i<=m;++i) ans=max(ans,f[1][i]); cout<<ans<<endl;
    //根据dp方程的推导，以1为根选取1~m个节点的最大值
}

望大佬们多多海涵，感谢斧正