[區間DP] Codeforces 392E Round #230 (Div. 1) E. Deleting Substrings

好水的E題

f[i][j]表示删完[i,j]區間的最大收益

g[i][j] 表示把[i,j]删成a[i], a[i]+1, a[i]+2 …a[j]的最大收益

h[i][j]類似g[i][j]，遞減

f[i][j] <- g[i][k]+h[k][j]+v[2*a[k]-a[i]-a[j]+1]

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

inline char nc(){
  static char buf[],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-;
  for (x=;c>='0' && c<='9';x=x*+c-'0',c=nc()); x*=b;
}

const int N=;

int n,a[N],v[N];
int f[N][N],g[N][N],h[N][N];
int ans[N];

int main(){
  freopen("haha.in","r",stdin);
  freopen("haha.out","w",stdout);
  read(n);
  for (int i=;i<=n;i++) read(v[i]); for (int i=;i<=n;i++) read(a[i]);
  for (int l=;l<=n;l++)
    for (int i=;i+l-<=n;i++){
      int j=i+l-;
      if (i==j){
    g[i][j]=,h[i][j]=;
    f[i][j]=v[];
    continue;
      }
      g[i][j]=h[i][j]=-<<;
      for (int k=i+;k<=j;k++)
    if (a[k]==a[i]+)
      g[i][j]=max(g[i][j],f[i+][k-]+g[k][j]);
    else if (a[k]==a[i]-)
      h[i][j]=max(h[i][j],f[i+][k-]+h[k][j]);
      f[i][j]=-<<;
      for (int k=i;k<j;k++)
    f[i][j]=max(f[i][j],f[i][k]+f[k+][j]);
      for (int k=i;k<=j;k++)
    if (g[i][k]>-<< && h[k][j]>-<<)
      f[i][j]=max(f[i][j],g[i][k]+h[k][j]+v[*a[k]-a[i]-a[j]+]);
    }
  for (int i=;i<=n;i++){
    ans[i]=ans[i-];
    for (int j=;j<=i;j++)
      ans[i]=max(ans[i],ans[j-]+f[j][i]);
  }
  printf("%d\n",ans[n]);
  return ;
}