洛谷P1091 合唱队形

概述本文章向大家介绍洛谷P1091 合唱队形，需要的朋友可以参考一下 @H_403_1@

输入输出样例

输入样例#1：

8

186 186 150 200 160 130 197 220

输出样例#1：

4

@H_403_1@

此题意在先升后降子序列，单调递增子序列，单调递减子序列当中找到最长的一组序列。

因此我们可以正向便利，1~n，i>=1&&i<=n,dp[i]为以第i个数结尾的单调递增子序列的长度。

dp[i]=max(dp[j],dp[i])(1<=j<=i&&a[j]<=a[i])a[i]为同学升高。

然后同理逆向跑一边，得到dp1数组 ，dp1[i]为以第i个结束的最长单调递增子序列。

最后我们从1~n便利一遍，ans=max（dp[i]+dp1[i]-1,ans）;n-ans为答案。。。。。

下面为代码：

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#define N 1000

int a[N],b[N],c[N];

int main()

{

int n;

scanf("%d",&n);

for(int i=1;i<=n;i++)

scanf("%d",&a[i]);

for(int i=1;i<=n;i++)

{

for(int k=i-1;k>=0;k--)

if(a[k]

b[i]=max(b[i],b[k]+1);

}

for(int i=n;i>=1;i--)

{

for(int k=i+1;k<=n+1;k++)

if(a[i]>a[k])

c[i]=max(c[i],c[k]+1);

}

int sum=0;

for(int i=1;i<=n;i++)

{

sum=max(sum,b[i]+c[i]-1);

}

printf("%dn",n-sum);

return 0;

}

总结

以上是内存溢出为你收集整理的洛谷P1091 合唱队形全部内容，希望文章能够帮你解决洛谷P1091 合唱队形所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。