输入输出样例

输入样例#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;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!