luogu P1091 [NOIP2004 提高组] 合唱队形

题目链接
难度：普及/提高-

一. 思路简述

本题比较简单，做完导弹拦截那题这道题基本就不用思考。故题解写的比较简单，不再赘述以往内容。

1. 理解题意，转化化归

很多题目看似五花八门，究其本质都是从最基本的题型演变而来。对于线性状态动态规划，一但我们掌握了最长上升子序列、最长公共子序列、导弹拦截这些题目，其他题目题目做起来也没得心应手。其中一个关键点在于，如何看清题目复杂描述的本质，恰当的转化化归，用基本题目的模型方法来做。

对于本题，首先求出列的最少人数也就是求队列中人的最多个数。又由队列满足限制 t 1 < t 2 ⋯ < t i > t ( i + 1 ) ⋯ > t k t_1<t_2\cdots<t_i>t_(i+1)\cdots>t_k t1​<t2​⋯<ti​>t(​i+1)⋯>tk​，显然可以先求以所有节点为终点的最长上升子序列的最大长度，再求以及以其为起点的最长下降子序列的最大，两者分别求和在取最大值。所得结果减去1即为队列中能容纳的最多人数。

2. 递推的顺序别搞错，始终要从已知推未知

本题最初时，我把代码错写成了如下这样：

for (int i = 0; i < n;i++)
{
    for (int j = 0; j < i;j++)
        if(h[j]<h[i])
            dp[i][0] = max(dp[j][0] + 1, dp[i][0]);
    for (int j = n-1; j > i;j--)
        if(h[j]<h[i])
            dp[i][1] = max(dp[j][1] + 1, dp[i][1]);
    dp[i][2] = dp[i][0] + dp[i][1];
}     

这里我把两个子序列的求解放到了一起，忽略了后一个循环递推并不满足从已知推未知，故错误。很多时候我们做题是盲目按照直接读取了数据的二维数组进行递推也会出现类似的错误，但就是发现递推的顺序是乱的，直接递推并不满足从已知到未知。这是往往要先进行排序等处理才方便解题。

二.代码

#include <bits/stdc++.h>
#define LEN 101
using namespace std;
int h[LEN] = {0};
int dp[LEN][3] = {0};
int main(){
    int n;
    while(cin>>n)
    {
        int sum = 0;
        for (int i = 0; i < n;i++)
        {
            cin >> h[i];
            dp[i][0] = 1;
            dp[i][1] = 1;
        }
        for (int i = 0; i < n;i++)
        {
            for (int j = 0; j < i;j++)
                if(h[j]<h[i])
                    dp[i][0] = max(dp[j][0] + 1, dp[i][0]);
        }
        for (int i = n-1; i >=0;i--)
        {
            for (int j = n-1; j > i;j--)
                if(h[j]<h[i])
                    dp[i][1] = max(dp[j][1] + 1, dp[i][1]);
            dp[i][2] = dp[i][0] + dp[i][1];
        }
        for (int i = 0; i < n;i++)
            sum = max(sum, dp[i][2]);
        cout << n - sum + 1 << endl;
    }
    return 0;
}