题意
给定一个长度为n的序列，你可以进行若干次操作：
选择一个区间，删掉，并获得Val[Len]的得分，Len为这个区间的长度：
其中这个区间满足：
1.相邻两个数差的绝对值为1
2.每个数都大于相邻两个数的平均数
问最大得分。
解法
一眼过去，得到一个可能是O(n^4)的做法。
设f[i][j]表示删除掉[i,j]这个区间的最大得分。
然后发现只有这个转移不了，然后又多设了一个g[i][j][0/1]，表示以a[i]开头的，以a[j]结尾的上升或下降的最大得分。
然后发现这个好像要多存一个个数，然后很倦生，然后就弃疗了。
赛后发现，其实标算跟我的做法差不多，多存一维个数可以用上升序列的性质直接算。
然后打着打着又发现了一个问题。
f[i][j]<-g[i][k]+g[k][j]的合并有点奇怪。
然后水过了之后再看标，恍然大悟。
靠这样转移就可以把两个g拼接起来了。
Code
#include<bits/stdc++.h>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fd(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
const int maxn=407,Inf=0x7fffffff;
int n,Val[maxn],a[maxn];
int Up[maxn][maxn],Dn[maxn][maxn];
void getUpDn(){
fo(i,1,n){
Up[i][i]=0;
fo(j,i+1,n){
if (Up[i][j-1]) Up[i][j]=Up[i][j-1];
else if (a[j]==a[j-1]+1) Up[i][j]=0;
else Up[i][j]=j;
}
}
fo(i,1,n){
Dn[i][i]=0;
fo(j,i+1,n){
if (Dn[i][j-1]) Dn[i][j]=Dn[i][j-1];
else if (a[j]==a[j-1]-1) Dn[i][j]=0;
else Dn[i][j]=j;
}
}
}
void Init(){
scanf("%d",&n);
fo(i,1,n) scanf("%d",&Val[i]);
fo(i,1,n) scanf("%d",&a[i]);
getUpDn();
}
int Check(int l,int r,int L=0,int R=0){
if (L){
if (r-l+1==0) return Check(L,R);
else if (R-L+1==0) return Check(l,r);
else{
int x=Up[l][r];
if (x==0){
if (a[r]+1==a[L]) return Check(L,R);
else if (a[r]-1==a[L]) return (Dn[L][R]==0)*2;
else return 0;
}else{
if (Dn[x-1][r]==0 && a[r]-1==a[L]) return (Dn[L][R]==0)*2;
else return 0;
}
}
}else{
if (l==r) return 1;
else{
int x=Up[l][r];
if (x==0) return 1;
else return (Dn[x-1][r]==0)*2;
}
}
}
int f[maxn][maxn],g[maxn],h[maxn][maxn][2],Ans=0;
void getF(){
fo(Len,2,n)
fo(i,1,n){
int j=i+Len-1;
if (j>n) break;
fo(k,i,j-1){
if (a[k]+1==a[j]) h[i][j][0]=max(h[i][j][0],h[i][k][0]+f[k+1][j-1]);
if (a[k]-1==a[j]) h[i][j][1]=max(h[i][j][1],h[i][k][1]+f[k+1][j-1]);
}
fo(k,i,j-1){
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
}
fo(k,i,j-1)
if (h[i][k][0]>-1e8 && h[k][j][1]>-1e8)
f[i][j]=max(f[i][j],h[i][k][0]+h[k][j][1]+Val[a[k]-a[i]+a[k]-a[j]+1]);
if (h[i][j][0]>-1e8) f[i][j]=max(f[i][j],h[i][j][0]+Val[a[j]-a[i]+1]);
if (h[i][j][1]>-1e8) f[i][j]=max(f[i][j],h[i][j][1]+Val[a[i]-a[j]+1]);
}
}
void getG(){
g[0]=0;
fo(i,1,n){
g[i]=g[i-1];
fo(j,0,i-1){
g[i]=max(g[i],g[j]+f[j+1][i]);
}
}
}
void Solve(){
fo(i,1,n) fo(j,1,n) f[i][j]=h[i][j][0]=h[i][j][1]=-1e9;
fo(i,1,n){
f[i][i-1]=0;
fo(j,i,n){
if (Check(i,j)) f[i][j]=Val[j-i+1];
else f[i][j]=-1e9;
if (j>i) h[i][j][0]=h[i][j][1]=-1e9;
else h[i][j][0]=h[i][j][1]=0;
}
}
getF();
getG();
Ans=g[n];
}
void Print(){
printf("%d
",Ans);
}
int main(){
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
Init();
Solve();
Print();
return 0;
}