欢迎光临散文网 会员登陆 & 注册

USACO金牌题目 Brakets (range DP)

2022-09-26 11:34 作者:信奥赛USACO郑老师  | 我要投稿

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

}


USACO金牌题目 Brakets (range DP)的评论 (共 条)

分享到微博请遵守国家法律