首页 > 其他 > 详细

Luogu1091 合唱队形

时间:2018-04-27 20:55:55      阅读:174      评论:0      收藏:0      [点我收藏+]

线性动态规划

思路:一遍算出最长不降子序列,再一遍算出最长不升子序列,再一遍历维护max求出答案。

#include<iostream>
using namespace std;
int n,t[105],fd[105],ans,fu[105];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>t[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            if(t[i]>t[j])
                fd[i]=max(fd[i],fd[j]+1);
    for(int i=n;i>0;i--)
        for(int j=n+1;j>i;j--)
            if(t[i]>t[j])
                fu[i]=max(fu[i],fu[j]+1);
    for(int i=1;i<=n;i++)
        ans=max(ans,fu[i]+fd[i]-1);
    cout<<n-ans;
    return 0;
}

Luogu1091 合唱队形

原文:https://www.cnblogs.com/pushinl/p/8964198.html

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