C# · 12月 20, 2021

洛谷P1091 合唱队形

输入输出样例

输入样例#1:

8

186 186 150 200 160 130 197 220

输出样例#1:

4

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

因此我们可以正向便利,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;

}