Maximum Monogonosity

· · 题解

这种题在场上没做出来我还是挺飞舞的。

设 \omega(i,j)=|b_i-a_j|+|b_j-a_i|，首先显然的 dp 是 f(i,j) 表示 前 i 个数，已经有 j 长度的最大价值。

转移则是简单的，f(i,j)=\max(f(i-1,j),\max\{f(i-x,j-x)+\omega(i-x+1,i)\})。即将 [i-x+1,i] 这个长为 x 的纳入；或者目前不选 i。

这个东西 i,j,x 的枚举时 n\times k\times k 的，没法通过，考虑优化。

我们发现，如果要选 i，则转移过来的 f(i^\prime,j^\prime) 其 i^\prime-j^\prime=i-j。那么，我们尝试将 i-j 相同的的归为一类。

但是我们发现还有个绝对值不太好搞，我们将 \omega(i,j) 拆开：

f(i,j)=\max\left\{ \begin{aligned} b_i-a_i+f(i-x,j-x)-a_{i-x+1}+b_{i-x+1}\\ b_i+a_i+f(i-x,j-x)-a_{i-x+1}-b_{i-x+1}\\ -a_i-b_i+f(i-x,j-x)+a_{i-x+1}+b_{i-x+1}\\ -b_i+a_i+f(i-x,j-x)+a_{i-x+1}-b_{i-x+1}\\ \end{aligned} \right.

我们将只和 i 有关的 a_i,b_i 不看，发现似乎只需要维护对于 i-j=m 的最大 f(i,j) 加上一些玩意。为什么这样就可以得到正确的结果呢？我们只要证明两个点，第一不会枚举到不存在的更优解，第二一定能枚举到合法的最优解。

对于第一条，由于 |x|\ge x，绝对值拆开后，必然拆不出比原来更大的结果，所以成立。

对于第二条，绝对值所有取值情况都枚举过了，而且最开始枚举了一个不取的情况，所以是成立的。

那么代码比较显然了。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(i=l; i<=r; ++i)
const int N=3005, K=3005;
using ll=long long;
vector<ll> mxa, mxb, mxc, mxd;
/*
- + a - +
+ + b - -
- - c + +
+ - d + -
*/
long long f[N][K], a[N], b[N];
int n, k, i, j, t;
long long ret;
const ll inf=-(1ll<<50);
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        ret=0;
        scanf("%d %d", &n, &k);
        rep(i, 1, n) scanf("%lld", a+i); a[n+1]=0;
        rep(i, 1, n) scanf("%lld", b+i); b[n+1]=0;
        vector<ll>(n+5, inf).swap(mxa); vector<ll>(n+5, inf).swap(mxb);
        vector<ll>(n+5, inf).swap(mxc); vector<ll>(n+5, inf).swap(mxd);
        rep(i, 0, n) rep(j, 0, n) f[i][j]=inf;
        f[0][0]=0; mxa[0]=-a[1]+b[1]; mxb[0]=a[1]+b[1]; mxc[0]=-a[1]-b[1]; mxd[0]=a[1]-b[1];
        rep(i, 1, n)
        {
            rep(j, 0, k)
            {
                if(j>i) break;
                f[i][j]=max(f[i][j], f[i-1][j]);
                f[i][j]=max(f[i][j], -a[i]+b[i]+mxa[i-j]);// printf("%d %d\n",mxa[i-j],f[i][j]);
                f[i][j]=max(f[i][j], -a[i]-b[i]+mxb[i-j]);// printf("%d\n",f[i][j]);
                f[i][j]=max(f[i][j], +a[i]+b[i]+mxc[i-j]);// printf("%d\n",f[i][j]);
                f[i][j]=max(f[i][j], +a[i]-b[i]+mxd[i-j]);// printf("%d\n",f[i][j]);
                if(i!=n)
                {
                    mxa[i-j]=max(mxa[i-j], f[i][j]-a[i+1]+b[i+1]);
                    mxb[i-j]=max(mxb[i-j], f[i][j]+a[i+1]+b[i+1]);
                    mxc[i-j]=max(mxc[i-j], f[i][j]-a[i+1]-b[i+1]);
                    mxd[i-j]=max(mxd[i-j], f[i][j]+a[i+1]-b[i+1]);
                }
                ret=max(ret, f[i][j]);
            }
        }
        printf("%lld\n", ret);
    }
}