讨论 / AC代码之一,用时最多的点用了5ms
dengping 2015-10-31 22:08:34
点我顶贴 收藏 删除
#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

int n,h[150];

int dp[150][2];//dp[i][0]是上升序列,dp[i][1]是下降序列

int main() {

scanf("%d",&n);

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

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

}

dp[1][0]=1;

dp[n][1]=1;

for (int i=2;i<=n;i++) {

int maxx=0;

for (int j=i-1;j>=1;j--) {

if (h[j]<h[i] && dp[j][0]>maxx) {

maxx=dp[j][0];

}

}

dp[i][0]=maxx+1;

//printf("dp[%d][%d]:%d\n",i,0,dp[i][0]);

}

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

int maxx=0;

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

if (h[j]<h[i] && dp[j][1]>maxx) {

maxx=dp[j][1];

}

}

dp[i][1]=maxx+1;

//printf("dp[%d][%d]:%d\n",i,1,dp[i][1]);

}

int ans=0;

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

int f1=0,f2=0;

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

if (h[i]<h[k]) {

f1=max(f1,dp[i][0]);

}

}

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

if (h[i]<h[k]) {

f2=max(f2,dp[i][1]);

}

}

ans=max(ans,f1+f2+1);

}

printf("%d\n",n-ans);

return 0;

}

查看更多回复
提交回复