本文共 837 字,大约阅读时间需要 2 分钟。
//合唱队形#include#include using namespace std;int N;int main(){ scanf("%d",&N); int h[N+5]; for(int i = 1; i<= N; i++) scanf("%d",&h[i]); //先从左到右求最长上升子序列 int dp1[N+5] = {0, 1}; for(int i = 2; i<= N; i++){ int tmp = 0; for(int j = 1; j < i; j++) if(dp1[j] > tmp && h[i] > h[j]) tmp = dp1[j]; dp1[i] = tmp + 1; } //再从右到左求最长上升子序列 int dp2[N+5]; dp2[N] = 1; for(int i = N-1; i >= 1; i--){ int tmp = 0; for(int j = N; j > i; j--) if(dp2[j] > tmp && h[i] > h[j]) tmp = dp2[j]; dp2[i] = tmp + 1; } //找出dp1和dp2的最大和 int sum = 0, ans; for(int i = 1; i <= N; i++){ if(dp1[i] + dp2[i] > sum) sum = dp1[i] + dp2[i]; } ans = N-sum; printf("%d",ans+1); return 0;}
转载地址:http://hezdf.baihongyu.com/