https://codeforces.com/contest/1310/problem/B
有$2^{n}$名选手参加比赛，比赛分两组，一组是正常组，一组是淘汰组，刚开始$2^n$名选手都在正常组中，失败选手进入淘汰组
淘汰组每轮进行两次比赛，首先是两两比赛，然后是和正常组的失败选手比赛，给出$k$名人气选手，求最多有多少场比赛里面有人气选手参与
定义$dp[i][j][up][down],i\in [1,n], up\in \left \{ 0,1\right \} $表示只考虑编号在$\left [j,j+2^i \right )$的选手,如果up为$1$,保证正常组胜出的是人气选手，否则为普通选手，如果down为$1$,保证淘汰组胜出的是人气选手，否则为普通选手，最大有人气选手的比赛场次
$dp[i][j]$由$dp[i-1][j]$和$dp[i-1][j+2^{i-1}]$转移过来，总共有八种情况
参考博客：https://www.cnblogs.com/heyuhhh/p/12363999.html
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100+7;
const int INF=0x3f3f3f3f;
int n,k,fan[(1<<17)+7];
int dp[18][(1<<17)+7][2][2];
int main(){
scanf("%d %d",&n,&k);
for(int i=1;i<=k;i++){
int x;
scanf("%d",&x);
fan[x]=1;
}
memset(dp,-INF,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=1;j<=(1<<n);j+=(1<<i)){
if(i==1){
dp[i][j][fan[j]][fan[j+1]]=(fan[j]|fan[j+1]);
dp[i][j][fan[j+1]][fan[j]]=(fan[j]|fan[j+1]);
continue;
}
for(int x1=0;x1<2;x1++){
for(int x2=0;x2<2;x2++){
for(int y1=0;y1<2;y1++){
for(int y2=0;y2<2;y2++){
int cost=dp[i-1][j][x1][y1]+dp[i-1][j+(1<<(i-1))][x2][y2];
if(x1|x2)cost++;
if(y1|y2)cost++;
dp[i][j][x1][x2]=max(dp[i][j][x1][x2],cost+(x2|y1));
dp[i][j][x1][x2]=max(dp[i][j][x1][x2],cost+(x2|y2));
dp[i][j][x1][y1]=max(dp[i][j][x1][y1],cost+(x2|y1));
dp[i][j][x1][y2]=max(dp[i][j][x1][y2],cost+(x2|y2));
dp[i][j][x2][x1]=max(dp[i][j][x2][x1],cost+(x1|y1));
dp[i][j][x2][x1]=max(dp[i][j][x2][x1],cost+(x1|y2));
dp[i][j][x2][y1]=max(dp[i][j][x2][y1],cost+(x1|y1));
dp[i][j][x2][y2]=max(dp[i][j][x2][y2],cost+(x1|y2));
}
}
}
}
}
}
int ans=-INF;
ans=max(ans,dp[n][1][0][1]+1);
ans=max(ans,dp[n][1][0][0]+0);
ans=max(ans,dp[n][1][1][1]+1);
ans=max(ans,dp[n][1][1][0]+1);
printf("%d\n",ans);
return 0;
}
codeforces#1310B. Double Elimination（动态规划）
原文：https://www.cnblogs.com/carcar/p/12373794.html