题解：P1389 一个关于序列的游戏

· · 题解

区间 dp 好题，思路容易考虑不周或假掉。

首先看到这个数据范围，一眼区间 dp，然后考虑如何做。

我们观察一下这个符合要求的区间的限制，一个是 |a_i-a_{i+1}|\leq 1 这个很好处理，但是下一个条件转化成式子就是 a_{i+1} \geq \frac{1}{2} (a_{i}+a_{i+2})，这是啥意思？

我们一眼发现这个东西得是一个凸的东西，一直单增或单减显然合法，然后考虑发现单峰也是合法的！

我们可以考虑证明：

若存在单峰，则 a_{i+2}=a_{i+1}+1=a_i+2，然后将这个式子带入条件:

a_i+1=a_{i+1}=\frac{1}{2}(a_i+a_i+2)=a_i+1

则可以证明是正确的，而单谷却不行，读者可以自行证明。

那找到了这个性质之后就可以 dp 了。

设 f_{i,j} 表示将 [i,j] 这一段全部删光的最大分数。

设 g_{i,j} 表示将 [i,j] 这一段删成单调递增，且保留 i 和 j位置的最大分数。

设 h_{i,j} 表示将 [i,j] 这一段删成单调递减且保留 i 和 j位置的最大分数。

考虑如何转移，对于 g，显然有：

g_{i,j}=g_{i,k}+f_{k+1,j-1}

类似地，对于 h，有：

g_{i,j}=g_{i,k}+f_{k+1,j-1}

那这个时候可能会有人有疑问了，假如说我删去 [i,j] 中间的一段 [l,r]，满足 i<l\leq r<j，那这样岂不是转移不到？

答案是可以转移到的，我们考虑每一次进行转移都会留下来右端点 j，然后在下一次转移的时候当我的 k 为现在的 j 的时候我又会删掉一些新的，和我直接删掉一部分是等价的。

而我们对于 f 的转移，则有两种。

  1. i$ 和 $j$ **不同时**被消掉，即 $f_{i,j}=f_{i,k}+f_{k+1,j}
  2. 先删掉一部分，最后将 l 和 r 同时删掉，即 f_{i,j}=g_{i,k}+h_{k,j}+v_{a_k\times 2-a_i-a_j+1}，这其中加的东西是因为是单峰的，将中间的减去两边的相加 +1 即可算出长度。

最后统计答案，简单 dp 计算即可。

#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_start;
constexpr int N=155;
int _=1,n,ans=0,v[N],a[N],dp[N],f[N][N],g[N][N],h[N][N];
inline int reads(){
    int c=getchar(),x=0,f=1;
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
    return x*f;
}inline void files(){
    freopen("good.in","r",stdin);
    freopen("good.out","w",stdout);
}inline void clr(){
//  Don't forget!

}bool Test_MLE_end;
signed main(){
//  printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
    files();
//  _=reads();
    while(_--){
        clr();n=reads();
        for(int i=1;i<=n;i++) v[i]=reads();
        for(int i=1;i<=n;i++) a[i]=reads();
        memset(g,-0x3f,sizeof(g));memset(h,-0x3f,sizeof(h));
        memset(f,-0x3f,sizeof(f));
        for(int i=1;i<=n;i++) g[i][i]=h[i][i]=f[i][i-1]=0,f[i][i]=v[1];
        for(int len=2;len<=n;len++){
            for(int i=1;i+len-1<=n;i++){
                int j=i+len-1;
                for(int k=i;k<j;k++){
                    if(a[k]+1==a[j]) g[i][j]=max(g[i][j],g[i][k]+f[k+1][j-1]);
                    if(a[k]-1==a[j]) h[i][j]=max(h[i][j],h[i][k]+f[k+1][j-1]);
                    f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
                }for(int k=i;k<=j;k++){
                    int t=a[k]+a[k]-a[i]-a[j]+1;
                    if(t<0||t>n) continue;
                    f[i][j]=max(f[i][j],g[i][k]+h[k][j]+v[a[k]+a[k]-a[i]-a[j]+1]);
                }
            }
        }for(int i=1;i<=n;i++){
            dp[i]=dp[i-1];
            for(int j=0;j<i;j++) dp[i]=max(dp[i],dp[j]+f[j+1][i]);
            ans=max(ans,dp[i]);
        }printf("%lld\n",ans);
    }return 0;
}