U486684 「INOI2016」Brackets 题解
首先对于回文 & 括号有一个经典转移：枚举分割点+区间两个端点讨论
此题也是如此
首先枚举分割点十分套路，如下
\[dp_{i,j}=\max_{k=i}^{j-1} dp_{i,k}+dp_{k+1,j}
\]
如果两个端点相同
\[dp_{i,j}=dp_{i+1,j-1}+v_i+v_j
\]
还有一个转移
对于一个区间，因为是子序列，所以一个区间的子区间也应该贡献答案
即：
\[dp_{i,j}=max(dp_{i+1,j},dp_{i,j-1})
\]
就是一个容斥
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=705;
int dp[N][N];
int a[N],b[N];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int len=2;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
if(b[i]+k==b[j]) dp[i][j]=max(dp[i][j],dp[i+1][j-1]+a[i]+a[j]);
dp[i][j]=max(dp[i][j],max(dp[i+1][j],dp[i][j-1]));
for(int k=i;k<j;k++)
{
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
cout<<dp[1][n];
return 0;
}