首页 > 其他 > 详细

【动态规划】合唱队形 luogu-

时间:2018-09-25 22:43:49      阅读:168      评论:0      收藏:0      [点我收藏+]

分析

做两遍最长上升子序列,在遍历一下,取最大值。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ms(a,b) memset(a,b,sizeof(a))
typedef long long ll;
int a[105];
int dp1[105],dp2[105];
inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int main(int argc,char* argv[]){
    int n=read();
    for (int i=1;i<=n;i++) a[i]=read(),dp1[i]=1,dp2[i]=1;
    for (int i=1;i<=n;i++) 
        for (int j=1;j<i;j++) 
            if (a[j]<a[i]) dp1[i]=max(dp1[i],dp1[j]+1);
    for (int i=n;i>=1;i--) 
        for (int j=n;j>i;j--) 
            if (a[j]<a[i]) dp2[i]=max(dp2[i],dp2[j]+1);
    int ans=0;
    for (int i=1;i<=n;i++) ans=max(ans,dp1[i]+dp2[i]);
    printf("%d\n",n-ans+1);
    return 0;
}

【动态规划】合唱队形 luogu-

原文:https://www.cnblogs.com/Dawn-Star/p/9703761.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!