CF1580D Subsequence 题解

天命之路 · 2021-10-04 16:01:25 · 题解

第一眼看到这个题目的时候，我们要关注这个式子的特点，并尝试用人话把他翻译一下

所以，原式 = 子序列和 \times 子序列长度 - 每对子序列中的点所框起的区间的最小值之和

首先看到后面那两个 \sum ，先把 i=j 的特殊情况去掉再说

则原式 = \sum\limits_{i=1}^m (m-1)*a_{b_i} - \sum\limits_{i=1}^m\sum\limits_{j=1,i\ne j}^m f(\min(b_i,b_j),\max(b_i,b_j))

​ =\sum\limits_{i=1}^m (m-1)*a_{b_i} - 2*\sum\limits_{i=1}^m\sum\limits_{j=i+1}^m f(b_i,b_j)

注意到在后面的 \sum 中，每个 b_i 被算 m-1 次，恰好与 前面对应，所以拆进去

则原式化为 \sum\limits_{i=1}^m\sum\limits_{j=i+1}^m a_{b_i} +a_{b_j} -2*f(b_i,b_j)

如果做惯了数论题，或许你猛然就会有一个直觉，这跟树上两点间的距离实在太像了

树上两点间的距离为 \operatorname{dep}[x]+\operatorname{dep}[y]-2*\operatorname{dep}[\operatorname{lca}(x,y)]

这里为 a_{b_i}+a_{b_j} - 2 * \min\limits_{k=b_i}^{b_j} a_k

我们思考怎么转换

所以我们要构造一棵带权的树，他满足任意两点间的 \operatorname{lca} 为原序列中此二数所夹子区间的最小值所在位置

则 w = dep_i - dep_{fa_i} = (a_i - d) -(a_{fa_i} - d) = a_i - a_{fa_i}

于是，这题就转换为在树上找 m 个点，使得他们两两之间的距离之和最大

树上背包即可

#include <bits/stdc++.h>
using namespace std;
const int N=4e3+5;
int ls[N],rs[N],stk[N],top=0,lw[N],rw[N],a[N],n,m;
int sze[N];
typedef long long ll;
ll f[N][N];
inline void dfs(int x)
{
    sze[x] = 1;
    if(ls[x])
    {
        dfs(ls[x]);
        for(int i=min(m,sze[x]);i>=0;i--)
            for(int j=min(m,sze[ls[x]]);j>=0;j--)
                f[x][i+j] = max(f[x][i+j],f[x][i] + f[ls[x]][j] + 1ll*j*(m-j)*lw[x]);
        sze[x] += sze[ls[x]];
    }
    if(rs[x])
    {
        dfs(rs[x]);
        for(int i=min(m,sze[x]);i>=0;i--)
            for(int j=min(m,sze[rs[x]]);j>=0;j--)
                f[x][i+j] = max(f[x][i+j],f[x][i] + f[rs[x]][j] + 1ll*j*(m-j)*rw[x]);
        sze[x] += sze[rs[x]];
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int tmp = top;
        while(top && a[stk[top]]>a[i]) rs[stk[top-1]]=stk[top],top--;
        if(top<tmp) ls[i]=stk[top+1];
        stk[++top] = i;
    }
    while(top) rs[stk[top-1]]=stk[top],top--;

    for(int i=1;i<=n;i++)
    {
    //  printf("%d,%d\n",ls[i],rs[i]);
        if(ls[i]) lw[i] = abs(a[i]-a[ls[i]]);
        if(rs[i]) rw[i] = abs(a[i]-a[rs[i]]);
    }
    int minn=0x7f7f7f7f,pos=0;

    for(int i=1;i<=n;i++)
        if(a[i]<minn)minn=a[i],pos=i;
    assert(stk[1] == pos);
    dfs(pos);
    printf("%lld\n",f[pos][m]);
    return 0;
}

你或许会奇怪于这个写法的时间复杂度为何是 O(n^2) 的

观察树上背包时，我们其实是把两个集合 S 和 T 合并，花费 |S|*|T| 的代价

接下来又是一个奇妙的转化

我们建立一张 n 个点的无向图，初始没有边

每当我们要合并点集 S 和 T 时，就把 S 中的每一个点向 T 中的每一个点连边

显然，因为 S \cap T = \varnothing ,所以我们不会连出重边

所以每一条边就代表着 O(1) 的复杂度

而 n 个点的无向图连到最后，最多只有 \frac{n(n-1)}{2} 条边

所以时间复杂度为 O(n^2)

你可以认为这是一种势能分析的思想

完结撒花 ！！！