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;
}