注意到把对局在图上表示出来是一颗满二叉树(叶节点为选手,其他点为对局),可以考虑树形 dp。
设 \(x\) 为 \([l_x,r_x]\) 之间选手的比赛,且该节点到叶子结点距离 \(d_x\)。
设 \(f(x,p)\) 表示胜者为 \(p\) 的最大钱数,有转移:
\[\begin{aligned} f(x,p)&=f(lson(x),p)+g(rson(x))+a_{p,d_x}-a_{p,d_x-1}\quad (p\in[l_x,mid])\\ f(x,p)&=g(lson(x))+f(rson(x),p)+a_{p,d_x}-a_{p,d_x-1}\quad (p\in(mid,r_x]) \end{aligned} \]其中 \(g_x=\max_{i=l_x}^{r_x}f(x,i)\)。
注意到一共 \(N\) 层,所以每个叶节点一共只会给祖先贡献 \(N\) 个状态,一共 \(2^N\) 个叶节点。
所以复杂度 \(O(N2^N)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1 << 17) + 5, K = 17;
ll f[K][N], g[N];
int n, a[N][K];
void dp(int l, int r, int x, int lev)
{
int mid = l + r >> 1;
int lenl = mid - l + 1, lenr = r - mid, len = r - l + 1;
if(l == r)
{
f[lev][l] = 0;
return;
}
dp(l, mid, x << 1, lev - 1);
dp(mid + 1, r, x << 1 | 1, lev - 1);
for(int j = l; j <= mid; j ++)
f[lev][j] = f[lev - 1][j] + a[j][lev] - a[j][lev - 1] + g[x << 1 | 1];
for(int j = mid + 1; j <= r; j ++)
f[lev][j] = f[lev - 1][j] + a[j][lev] - a[j][lev - 1] + g[x << 1];
for(int i = l; i <= r; i ++)
g[x] = max(g[x], f[lev][i]);
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n;
for(int i = 0; i < (1 << n); i ++)
{
for(int j = 1; j <= n; j ++)
cin >> a[i][j];
}
dp(0, (1 << n) - 1, 1, n);
cout << g[1];
return 0;
}
标签:int,题解,rson,mid,ABC263F,节点,dp
From: https://www.cnblogs.com/adam01/p/18327142