[JLOI2015]战争调度【暴力+树形Dp】

Online Judge：Bzoj4007，Luogu P3262

Label：暴力，树形Dp

题解

参考了这篇blog https://www.cnblogs.com/GXZlegend/p/8300883.html。

定义状态\(dp[i][j]\)，表示以i为根的子树中有j个叶子节点打战的收益。

由于是一棵标准的完全二叉树，所以转移时用类似背包的方式合并两棵子树的贡献。

能产生贡献的只有平民（叶子节点），所以递归到叶子时才能计算贡献，而这个贡献值还与祖先的选择有关，所以必须在之前递归的时候，给那些祖先是否打战打上标记——也就是暴力枚举非叶子节点的选择。

整个算法看似很暴力，但实际因为其特殊的树形结构，dfs函数的调用次数不会太多，详细证明可以看上面那个博客。下面是本地测试dfs调用次数的结果，可以看到当n<=10时，dfs不会调用太多次，而每次递归时合并子树的复杂度也不大，所以这个数据范围完全没问题。

n= dfs调用次数 1 1 2 5 3 21 4 85 5 341 ... ... 10 349525

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
int dp[1050][520],w[2][1050][11];
/*
dp[i][j]:i的子树中有j个叶子节点打战的收益 
w[0/1][i][j]:题目给定，叶子节点i(0:作战，1：后勤)时对其第j个祖先的贡献
mark[i]:对于叶子，i这个深度的祖先，是否选择去打战
*/
bool mark[12];
int n,m;
void dfs(int x,int dep){
    for(int i=0;i<=(1<<dep);i++)dp[x][i]=0;
    
    if(!dep){
        for(int i=1;i<=n;i++){
            if(mark[i])dp[x][1]+=w[0][x][i];
            else dp[x][0]+=w[1][x][i];
        }
        return;
    }
    
    mark[dep]=0,dfs(x<<1,dep-1),dfs(x<<1|1,dep-1);
    for(int l=0;l<=1<<(dep-1);l++)for(int r=0;r<=1<<(dep-1);r++){
        dp[x][l+r]=max(dp[x][l+r],dp[x<<1][l]+dp[x<<1|1][r]);
    }

    mark[dep]=1,dfs(x<<1,dep-1),dfs(x<<1|1,dep-1);
    for(int l=0;l<=1<<(dep-1);l++)for(int r=0;r<=1<<(dep-1);r++){
        dp[x][l+r]=max(dp[x][l+r],dp[x<<1][l]+dp[x<<1|1][r]);
    }
}
int main(){
    scanf("%d%d",&n,&m);n--;
    int leaf=1<<n;
    
    for(int o=0;o<=1;o++)for(int i=0;i<leaf;i++)for(int j=1;j<=n;j++){
        scanf("%d",&w[o][i+leaf][j]);
    }
    
    dfs(1,n);
    int ans=0;
    for(int i=0;i<=m;i++)ans=max(ans,dp[1][i]);
    printf("%d\n",ans);
    return 0;
}