洛谷 P1091 合唱队形

嗯...

 

题目链接：https://www.luogu.org/problemnew/show/P1091

很明显这是一道dp题，求最长上升/下降子序列...

但这道题中既有上升序列，也有下降序列，所以我们把 f 数组设成二维，f[i][1]表示开始的上升子序列，f[i][2]表示后来的下降子序列（其实可以开两个数组）。依次枚举每一个点，把它当做中间最高的那一个，然后求出它的最长上升/下降子序列，最后枚举一遍，找一个最长的即可。

 

动态转移方程（首先要判断是否符合上升/下降）：

f[i] = max (f[i], f[j] + 1);

AC代码：

#include<cstdio>
#include<iostream>

using namespace std;

int f[305][3], t[105], ans;

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &t[i]);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++){
            if(t[j] < t[i]) f[i][1] = max(f[i][1], f[j][1] + 1);//首先要判断 
        }
    }     
    for(int i = n; i >= 1; i--){
        for(int j = n + 1; j > i; j--){
            if(t[i] > t[j]) f[i][2] = max(f[i][2], f[j][2] + 1);
        }
    }
    for(int i = 1; i <= n; i++){
        ans = max(ans, f[i][2] + f[i][1] - 1);//ans是队列中人数 
    }
    printf("%d
", n - ans);
    return 0;
}