[AtCoder Beginner Contest 263]F - Tournament（DFS记忆化搜索 + DP）

题目传送门：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)。

代码 / 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;
}