首页 > 其他分享 >ABC263F 题解

ABC263F 题解

时间:2024-07-27 16:52:25浏览次数:17  
标签:int 题解 rson mid ABC263F 节点 dp

题面

注意到把对局在图上表示出来是一颗满二叉树(叶节点为选手,其他点为对局),可以考虑树形 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

相关文章

  • ABC262F 题解
    题面把“移动\(a_n\)至数列头”称为rotate,删除一项称为erase。因为要求字典序最小,所以可以逐位贪心。考虑一个数\(a_i\)怎么变成第一个数:使用\(n-i\)次rotate/erase,再rotate一次。删除或移动原来的\(a_{i+1}\sima_n\),再移动原来的\(a_i\)(逐步移动到数列尾,再ro......
  • ABC261F 题解
    题面注意到如果两个球\(i,j\)有\(i<j,x_i>x_j\),那么这两个球一定会交换。所以要交换\(x\)的逆序对数次。但是相同颜色交换没有代价,所以答案是\(x\)的逆序对数减去满足\(c_i=c_j,i<j,x_i>x_j\)的\((i,j)\)对的数量。可以对每个\(j\)都求一遍满足\(c_i=j\)的\(......
  • ABC264F 题解
    题面注意到操作只对当前行/列有效,所以只要记录当前所在行和列是否有被操作。设\(f(i,j,x,y)\)表示到了位置\((i,j)\),第\(i\)行是否被操作,第\(j\)列是否被操作的最小代价。转移:设\(col=c(i,j)\oplusx\oplusy\)。\[\begin{aligned}f(i+1,j,x2,y)&\xleftarrow......
  • ABC265F 题解
    题面\(O(nd^2)\)考虑\(f(i,j,k)\)表示dp到第\(i\)维,距离\(p,q\)曼哈顿距离\(j,k\)的方案数。考虑朴素转移:设\(dis=|p_{i+1}-q_{i+1}|\)。\[\begin{aligned}f(i+1,j+t,k+dis-t)&\getsf(i,j,k)&(0\leqt\leqdis)\quad&(1)\\f(i+1,j+d+t,k+t)&\ge......
  • 题解:CF1608F MEX counting
    题解:CF1608FMEXcounting与其他题解不同,本篇题解是运用辅助数组$g$来解决问题。虽然代码可能要繁琐一点,但是辅助数组的思路适用范围更广一点。首先还是转化为前$i$个数的$mex$在区间$[l_i,r_i]$内。我们用dp数组$f_{i,x,c}$表示处理到了第$i$个数,当前的mex为......
  • CF605E Intergalaxy Trips 题解
    Description\(n\)个点的有向完全图。\(i\toj\)的边每天出现的概率均为\(p_{i,j}\),若\(i=j\),有\(p_{i,j}=1\)。每天可以选择一条存在的出边走过去或停留在原地不动。求最优策略下从\(1\)到\(n\)的期望天数。\(n\le10^3\)。Solution设\(f_i\)表示\(i\)......
  • [题解]P2672 [NOIP2015 普及组] 推销员
    P2672[NOIP2015普及组]推销员为了便于操作,将住户信息按疲劳值从大到小排序。那么对于选\(X\)个住户,有\(2\)种情况:选疲劳值前\(X\)大的住户,答案即为\(\sum\limits_{i=1}^Xa[i]+2\times\max\limits_{i=1}^Xs[i]\)。选疲劳值前\(X-1\)大的住户,然后在剩下的住户中,距离比......
  • 《梦醒蝶飞:释放Excel函数与公式的力量》21.2 问题解决策略
     第21章:综合案例分析 21.2问题解决策略在综合案例分析中,解决问题的策略涉及多个步骤,从问题的识别、分析到实施解决方案和评估效果。通过系统的方法和多学科的知识,可以高效地解决复杂的问题。以下将介绍一个具体案例,并通过详细的步骤展示如何制定和实施问题解决策略。案例......
  • Codeforce 962 Div3 C~E 题解
    C题目大意​给定两个字符串a,b,q个询问,每次操作可以将a[i]赋值为任意一个字符,每次询问[l,r]区间内使得sorted(a[l,r])==sorted(b[l,r])的最小操作次数分析​ 不妨先考虑一个区间如何判断sorted后的字串是否相等,发现跟字符出现的次数有关,于是考虑前缀和预处理每一个26......
  • ABC273F Hammer 题解
    ABC273FHammer题解题目大意数轴上有\(n\)个锤子和\(n\)堵墙,第\(i\)个锤子位于\(x_i\),第\(i\)堵墙位于\(y_i\),第\(i\)个锤子可以对应的敲开第\(i\)堵墙。以原点为起点,给定终点\(t\),问最少移动多少个单位长度才能走到\(t\)。必须拿到对应锤子敲开墙才能走过这堵......