标签：return 比赛 int 题解 Tournament ABC263F leaf dp define

[ABC263F] Tournament Solution

目录

• [ABC263F] Tournament Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

给定 $ n $，存在 $ 2^n $ 个人站成一排进行比赛，比赛赛制按照类满二叉树进行，即每 $ 2i $ 和 $ 2i - 1 $ 两人进行比赛，胜利者进入下一层继续按照相同赛制比赛，直至最终剩余一人。若第 $ i $ 人获得了 $ j $ 场比赛的胜利，那么将获得 $ C_{i, j} $ 的奖金。你可以任意安排每场比赛的输赢，以最大化所有人的奖金和，求最大值。

Solution

挺有意思的一道题，不难但是需要一点智慧。

显然 DP，但 DP 的状态有多种均可，这里主要介绍一个写起来较为简单易懂的。

令 $ dp(p, i) $ 表示比赛进行到了满二叉树节点的 $ p $ 节点处，此时还需要比赛 $ i $ 次，定义为还需要比赛主要是为了在叶子节点的时候便于处理。

发现这个东西和朴素线段树十分相似，则对于满二叉树的叶子节点编号 $ leaf $，其代表的人的编号（这里从 $ 1 $ 开始编号）即为 $ leaf - 2^n + 1 $，也就是 $ leaf \oplus 2^n + 1 $。

所以对于所有叶子节点有 $ dp(leaf, i) = C_{leaf \oplus 2^n + 1, i} $，中间的转移也十分类似线段树，显然为：

\[dp(p, i) = \max(dp(lson_p, i + 1) + dp(rson_p, 0), dp(lson_p, 0) + dp(rson_p, i + 1)) \]

显然最终答案在根节点且剩余的比赛次数为 $ 0 $，即 $ dp(1, 0) $。

不难发现这个东西通过记忆化搜索来实现会更便捷一些。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define LS (p << 1)
#define RS (LS | 1)
#define MID ((gl + gr) >> 1)

template < typename T = int >
inline T read(void);

int N, powN;
ll dp[(1 << 16) << 2][20];
ll C[(1 << 16) + 10][20];

ll MakeDP(int p, int i){
    if(~dp[p][i])return dp[p][i];
    if(p >= N)return dp[p][i] = C[(p ^ N) + 1][i];
    return dp[p][i] = max(MakeDP(LS, i + 1) + MakeDP(RS, 0), MakeDP(LS, 0) + MakeDP(RS, i + 1));
}

int main(){
    memset(dp, -1, sizeof dp);
    N = 1 << (powN = read());
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= powN; ++j)C[i][j] = read();
    printf("%lld\n", MakeDP(1, 0));
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_12_30 初稿

标签：return,比赛,int,题解,Tournament,ABC263F,leaf,dp,define
From： https://www.cnblogs.com/tsawke/p/17032804.html