题目传送门: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; }
Comments NOTHING