[AtCoder Beginner Contest 263]F – Tournament(DFS记忆化搜索 + DP)

发布于 2022-08-10  448 次阅读


题目传送门:F - Tournament (atcoder.jp)

题意 / Problem

有\(2^N\)个人,从\(1 ~ N\)进行编号,进行N轮操作,每轮操作将第\(2i-1\)和第\(2i\)个人进行对战,每次对战都有一个人胜出,失败的人淘汰。

编号为i的人如果赢了j次,那么就可以获得\(C[i][j]\)的奖励。求所有人获得的最大的奖励之和。

思路 / Thought

显然是一颗完美二叉树,容易想到用dfs + 记忆化搜索的方法来进行dp。

那么如何表示状态呢,\(dp[i][j]\)表示编号为i的人,连赢了j次获得的最大奖励和。

dfs的参数为\(o\)树上的节点编号,\(win\)连胜次数。

因为是完美二叉树,所以向下拓展的方式为向左右儿子拓展,若当前节点为o,则左右儿子分别为\(o<<1\)和\(o << 1 | 1\)。

每次向下有两种方式,左赢右输或者左输右赢,取大即可。

递归的终点是当节点编号大于节点数了就返回叶子节点连赢\(win\)次的奖励。

答案就是dfs(1, 0)。

ABC263F

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int c[1 << 17][20], dp[1 << 19][20], N;
//注意dp要开4倍空间
 
int dfs(int o,int win)
{
	if(o >= (1 << N))return c[o - (1 << N) + 1][win];
	if(dp[o][win])return dp[o][win];
	
	int res = 0;
	res = max(dfs(o << 1, win + 1) + dfs(o << 1 | 1, 0), dfs(o << 1, 0) + dfs(o << 1 | 1, win + 1));
	return dp[o][win] = res; 
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> N;
	for(int i = 1;i <= (1 << N); ++ i)
		for(int j = 1;j <= N; ++ j)
			cin >> c[i][j];
	//input finished
	cout << dfs(1, 0) << '\n';
	return 0;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-08-10