题目：Vijos P1098 合唱队形

题意：

    实现中间高，两边低的队形，剔除的最少人数

分析：

    剔除最少人，即是队伍最长达到最大长度，分别实现升序、降序，相加最大为目标队形

    状态：dp1[i]表示i为终点的最大升序，dp2[i]表示i为起点的最大降序

    状态转移：

        dp1[i] = max(dp1[j] | i>j, a[i] > a[j]) + 1;dp2[i] = max(dp2[j] | i<j, a[i] > a[j]) + 1;

核心：

    ans = max(ans, dp1[i] + dp2[j] - 1);

代码：


#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <vector>using namespace std;#define INF 0x7f7f7f7fd
#define MAX 100+10
#define MIN -1e+10int dp1[MAX];
int dp2[MAX];
int h[MAX];int main()
{freopen("a.txt", "r", stdin);int n, i, j;while(~scanf("%d", &n)){for(i = 1; i<=n; i++){scanf("%d", &h[i]);}memset(dp1, 0, sizeof(dp1));for(i = 1; i<=n; i++) // 升序{dp1[i] = 1;for(j = 1; j<i; j++){if(h[i] > h[j])dp1[i] = max(dp1[i], dp1[j] + 1);}}memset(dp2, 0, sizeof(dp2));for(i = n; i>=1; i--) // 降序{dp2[i] = 1;for(j=i+1; j<=n; j++){if(h[i] > h[j])dp2[i] = max(dp2[i], dp2[j] + 1);}}int ans = 0;for(i = 1; i<=n; i++){ans = max(ans, dp1[i] + dp2[i] - 1);}printf("%d\n", n - ans);}return 0;
}