P7421 子序列 题解

· · 题解

官方题解。

upd 2021.3.7：将 p 的下标改成括号形式，避免了下标不清。

这题赛时 AC 人数甚至没有压轴鱼神的多项式题人多？

把式子的前几项和后几项写出来：

(a_{p(1)}-a_{p(0)})(p(l+1)-p(l))+(a_{p(2)}-a_{p(1)})(p(l)-p(l-1))+\cdots+(a_{p(l)}-a_{p(l-1)})(p(2)-p(1))+(a_{p(l+1)}-a_{p(l)})(p(1)-p(0))

很难贪心，考虑 dp。发现状态中只记单独一个位置不好 dp，式子中 i 与 l-i 相关，再观察发现它们是两两对应的，于是将它们捆起来 dp，也就是选择 p 的元素时，左边选一个右边同时选一个。

设计状态 f_{i,j} 表示左边选到 i，右边选到 j。转移方程是：

f_{i,j}=\max_{x<i,y>j}\{f_{x,y}+(a_i-a_x)(y-j)+(a_y-a_j)(i-x)\}

当然可以不转移，将 \{i,j\} 直接作为 p 的开头和结尾，即 a_i(n-j+1)-a_j\cdot i。

将 f 求出来后，求出答案要分三种情况：

复杂度瓶颈在求 f，考虑优化。

将转移方程中的括号拆开：

f_{i,j}=\max_{x<i,y>j}\{f_{x,y}+a_i\cdot y-a_i\cdot j-a_x\cdot y+a_x\cdot j+a_y\cdot i-a_y\cdot x-a_j\cdot i+a_j\cdot x\}

将只与 i,j 有关的东西提出来：

f_{i,j}=\max_{x<i,y>j}\{f_{x,y}+a_i\cdot y-a_x\cdot y+a_x\cdot j+a_y\cdot i-a_y\cdot x+a_j\cdot x\}-a_i\cdot j-a_j\cdot i

枚举 x，将 x 也看作一个定值：

f_{i,j}=\max_{x<i,y>j}\{a_x\cdot j+a_j\cdot x+f_{x,y}+a_i\cdot y-a_x\cdot y+a_y\cdot i-a_y\cdot x\}-a_i\cdot j-a_j\cdot i

然后发现，与 y 有关的部分中只有 i 和 x 没有 j。于是用 g_{i,x} 表示对于这对 (i,x) 最好的 y 产生的最大值，即：

g_{i,x}=\max_y\{f_{x,y}+a_i\cdot y-a_x\cdot y+a_y\cdot i-a_y\cdot x\}

这个东西中包含一个 f_{x,y} 比较烦，考虑一边求 f 一边更新 g。具体来说，枚举 i,j，在循环里要做这些事：

  1. 枚举 x，通过 g 快速计算 f_{i,j} 的值；
  2. 将 (i,j) 当做 g 中的 (x,y)，枚举 g 中的 i，更新 g。

这段还是看程序比较好懂吧，可以先跳到下面程序部分搞懂再往下。

然后，还有一点细节要注意：g 的式子里面 y 其实是要大于“j”，但是不能把 j 记下来（不然就爆炸了），要通过一些手段使得当前 g 中存的都是大于 j 的答案。于是外层枚举 j 并倒序枚举。

还有一个小问题：(i-1,j) 是不能转移到 (i,j) 的，但是如果内层循环 i 正序枚举，那么在 f_{i-1,j} 时更新了 g_{i,i-1},g_{i+1,i-1}\cdots；在 f_{i,j} 时需要的有 g_{i,i-1},g_{i,i-2}，其中 g_{i,i-1} 重复了，于是内层的 i 也要倒序循环。

时间复杂度 \mathcal O(n^3)，代码：

#include<bits/stdc++.h>
using namespace std;
long long a[305],f[305][305],g[305][305];
inline int read()
{
    char c=getchar();
    int x=0,y=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')
            y=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*y;
}
int main()
{
    int n=read(),i,j,k;
    long long ans=-1000000000000000000ll;
    for(i=1;i<=n;i++)
        a[i]=read();
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            g[i][j]=-1000000000000000000ll;
    for(j=n;j;j--)//外层枚举j并倒序枚举，上面有解释
        for(i=j-1;i;i--)//内层枚举i并倒序枚举，上面有解释
        {
            f[i][j]=a[i]*(n-j+1)-a[j]*i;//不转移的情况
            for(k=1;k<i;k++)//这里的k就是转移方程中的x
                f[i][j]=max(f[i][j],g[i][k]-a[i]*j+a[k]*j-a[j]*i+a[j]*k);
            ans=max(ans,f[i][j]+(a[j]-a[i])*(j-i));
            for(k=i+1;k<j;k++)//这里的k就是g[i][x]中的i
                g[k][i]=max(g[k][i],f[i][j]+a[k]*j-a[i]*j+a[j]*k-a[j]*i);
        }
    for(i=1;i<=n;i++)
        ans=max(ans,a[i]*(n-i+1)-a[i]*i);
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
            for(k=i+1;k<j;k++)
                ans=max(ans,f[i][j]+(a[k]-a[i])*(j-k)+(a[j]-a[k])*(k-i));
    printf("%lld",ans);
    return 0;
}