Solution
考虑 \(f_{i,j}\) 表示第 \(i\) 个人赢下了第 \(j\) 场的最大价值，答案即为 \(\max_{i=1}^{n}f_{i,m}\)。
然后考虑状态转移，令 \(l,r\) 为第 \(i\) 个人在打第 \(j\) 场比赛时的区间，\(mid\) 为区间中点，然后分为两种情况：
-
第 \(i\) 个人在左半部分，转移即为 \(f_{i,j}=f_{i,j-1}+\max_{k=mid+1}^{r}f_{k,j-1}+a_{i,j}-a_{i,j-1}\)。
-
第 \(i\) 个人在右半部分，转移即为 \(f_{i,j}=f_{i,j-1}+\max_{k=l}^{mid}f_{k,j-1}+a_{i,j}-a_{i,j-1}\)。
注意此时应该先枚举 \(j\)，否则会有后效性。
发现式子里带有区间 \(\max\)，预处理一下即可。时间复杂度为 \(O(n \times 2^n)\)。
考场代码奇丑无比。
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define x first
#define y second
#define debug() puts("-----")
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+10,M=20;
int n,m;
ll a[N][M],f[N][M];
ll g1[N][M],g2[N][M];
int Pow(int x,int k){
int res=1;
while(k){
if(k&1) res=res*x;
x=x*x; k>>=1;
} return res;
}
pii get(int i,int j){
int l=(i-1)/j+1,r=l*j;
l=(l-1)*j+1; return pii(l,r);
}
signed main(){
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
scanf("%lld",&m); n=pow(2,m); ll ans=0;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%lld",&a[i][j]);
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
int l=get(i,Pow(2,j)).x,r=get(i,Pow(2,j)).y,mid=l+r>>1;
if(i<=mid){
ll res=g1[mid+1][j-1]+a[i][j];
// if(j>=2){
// int L=get(i,Pow(2,j-1)).x,R=get(i,Pow(2,j-1)).y,Mid=L+R>>1;
// if(i<=Mid) res+=g2[Mid+1][j-2]; else res+=g2[L][j-2];
// }
f[i][j]=max(f[i][j],res+f[i][j-1]-a[i][j-1]);
// for(int k=mid+1;k<=r;k++){ ll res=0;
// if(j>=2) for(int p=l;p<=mid;p++) if(get(p,pow(2,j-2))!=get(i,pow(2,j-2))) res=max(res,f[p][j-2]);
// f[i][j]=max(f[i][j],f[i][j-1]+f[k][j-1]+a[i][j]-a[i][j-1]);
// }
} else{
ll res=g1[l][j-1]+a[i][j];
// if(j>=2){
// int L=get(i,Pow(2,j-1)).x,R=get(i,Pow(2,j-1)).y,Mid=L+R>>1;
// if(i<=Mid) res+=g2[Mid+1][j-2]; else res+=g2[L][j-2];
// }
f[i][j]=max(f[i][j],res+f[i][j-1]-a[i][j-1]);
// for(int k=l;k<=mid;k++){
// ll res=0;
// if(j>=2) for(int p=mid+1;p<=r;p++) if(get(p,pow(2,j-2))!=get(i,pow(2,j-2))) res=max(res,f[p][j-2]);
// f[i][j]=max(f[i][j],f[i][j-1]+f[k][j-1]+a[i][j]-a[i][j-1]);
// }
} ans=max(ans,f[i][j]);
} int p=Pow(2,j);
for(int i=1;i<=n;i+=p){
for(int k=i;k<=i+p-1;k++)
g1[i][j]=max(g1[i][j],f[k][j]);
} p=Pow(2,j-1);
for(int i=1;i<=n;i+=p){
for(int k=i;k<=i+p-1;k++)
g2[i][j-1]=max(g2[i][j-1],f[k][j-1]);
}
} printf("%lld\n",ans); return 0;
} /*
2
2 5
6 5
2 1
7 9
3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
3
7 8 6
9 5 3
9 6 5
4 3 3
2 1 3
5 6 7
9 1 2
10 8 9
2
4 9
3 6
5 3
2 7
*/