题解：P3262 [JLOI2015] 战争调度
liuchang09
·
·
题解
思路
很显然是树上的动态规划。设 f_{i,j} 表示以 i 为根节点，他有 j 个下属选择参加战争时的最大贡献。
对于树上动态规划，我们可以使用深度优先搜索。从第一个节点开始，先将储存最大贡献的数组初始化，再枚举他是否参加战争并用 war_x 表示，最后枚举他的两个子节点并转移状态，边界就是当前节点到达最大深度时返回。又因为题中所说：
一个平民会对他的所有直系上司有贡献度
如果一个一个枚举并将叶子结点对他的父节点的贡献值累加到 f_{i,j} 上显然不理智，因此我们可以将其累加到最底部的叶子结点上。
然后是动态转移方程，这个还是比较好想的：
最后是答案的统计，因为不多于 $m$ 个平民参加战争，因此答案为 $\max\{f_{1,i}\}(i \in [0,m])$。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1028;
int f[maxn][maxn];
int a[maxn][12],b[maxn][12];
bool war[12];
int n,m;
int k;//一共有k个平民
int ans=-1;
int lz(int x){return 2*x;}
int rz(int x){return 2*x+1;}
inline int read(){
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}
return x;
}
void dfs(int x,int y){//当前节点和当前层数
for(int j=0;j<=(1<<(n-y));j++)
f[x][j]=0;
if(y==n){
for(int i=1;i<=n;i++){
if(war[i]) f[x][1]+=a[x][i];
else f[x][0]+=b[x][i];
}
return ;
}
for(int w=0;w<=1;w++){
war[y]=w;
dfs(lz(x),y+1);
dfs(rz(x),y+1);
for(int i=0;i<=(1<<(n-y-1));i++)
for(int j=0;j<=(1<<(n-y-1));j++)
f[x][i+j]=max(f[x][i+j],f[lz(x)][i]+f[rz(x)][j]);
}
}
signed main(){
//freopen("test.in","r",stdin);
n=read();m=read();
k=(1<<(n-1));
for(int i=1;i<=k;i++)
for(int j=1;j<=n-1;j++)
a[k-1+i][n-j]=read();
for(int i=1;i<=k;i++)
for(int j=1;j<=n-1;j++)
b[k-1+i][n-j]=read();
dfs(1,1);
for(int i=0;i<=m;i++)
ans=max(ans,f[1][i]);
printf("%lld\n",ans);
return 0;
}
```