CF987C Three displays【一维DP/类似最大子序列和】

【链接】：CF987C

【分析】：先求出每个s【i】后面比s【i】大的c【i】的最小值，然后枚举前两个数c(i)，c(j)以及 j 后面递增且存在最小值的dp(j)

【代码】：

#include<bits/stdc++.h>

using namespace std;

const int  INF =  0x3f3f3f3f;

#define ms(a,b) memset(a,b,sizeof(a))

#define rep(i,a,b) for(int i=(a); i<=(b); i++)

//#define run(i,a,b) for(int i=(a); i<=(b); i++)

int n;

int s[3005];

int c[3005];

int dp[3005];    //dp【i】表示s【i】后面比s【i】大的对应c【i】的最小值

int main()

{

    ms(dp,INF);

    cin>>n;

    int ans=INF;

    rep(i,1,n)

      cin>>s[i];

    rep(i,1,n)

      cin>>c[i];

    rep(i,1,n)

    {

        rep(j,i+1,n)

        {

            if(s[j]>s[i])

                dp[i]=min(dp[i],c[j]);

        }

    }

    rep(i,1,n)

    {

        rep(j,i+1,n)

        {

            if(s[j]>s[i] && dp[i]!=INF)

            {

                ans = min(ans, c[i]+c[j]+dp[j]);

            }

        }

    }

    if(ans==INF) puts("-1");

    else cout<<ans<<endl;

}

巴特西

CF987C Three displays【一维DP/类似最大子序列和】

最新文章

热门文章