题解：P3262 [JLOI2015] 战争调度

思路

很显然是树上的动态规划。设

f_{i,j}

表示以

i

为根节点，他有

j

个下属选择参加战争时的最大贡献。

对于树上动态规划，我们可以使用深度优先搜索。从第一个节点开始，先将储存最大贡献的数组初始化，再枚举他是否参加战争并用

war_x

表示，最后枚举他的两个子节点并转移状态，边界就是当前节点到达最大深度时返回。又因为题中所说：

一个平民会对他的所有直系上司有贡献度

如果一个一个枚举并将叶子结点对他的父节点的贡献值累加到

f_{i,j}

上显然不理智，因此我们可以将其累加到最底部的叶子结点上。

然后是动态转移方程，这个还是比较好想的：

f_{i,j+k}=\max\{f_{i \times 2,j}+f_{i \times 2 + 1,k}\}(j,k \in [2^{n - 1},2^n - 1],i \in [1,2^n - 1])

。

最后是答案的统计，因为不多于

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;
}

题解：P3262 [JLOI2015] 战争调度

文章操作

思路

代码

相关推荐

评论

题解：P3262 [JLOI2015] 战争调度