USACO金牌题目 Brakets (range DP)
#include <bits/stdc++.h>
using namespace std;
int v[703],b[703];
int dp[703][703];
int main()
{
int k,n;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>v[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
int maxv=0;
for(int w=2;w<=n;w++){//substring width
for(int l=1;l<=n-w+1;l++){
int r=l+w-1;
int res=dp[l][r-1]+dp[r][r];
for(int t=l;t<=r-1;t++){
if(b[t]+k==b[r]){
res=max(res,dp[l][t-1]+v[t]+v[r]+dp[t+1][r-1]);
}
}
dp[l][r]=res;
maxv=max(maxv,res);
}
}
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<setw(3)<<dp[i][j];
}
cout<<endl;
}
*/
cout<<maxv<<endl;
return 0;
}