题目类型

最长上升子序列 + 贪心 + dfs:

给一组数，某个装备可以由大到小遍历，或者由小到大遍历，
问最少需要多少装备可以遍历所有的数


在拦截导弹(1010题https://www.acwing.com/problem/content/description/1012/)的基础上
加了一个判别由大到小还是由小到大。

用dfs进行判别这个装备是由大到小还是由小到大。

最该注意的地方：

while(k < su && h[u] <= up[k])  //在up[]中找到第一个小于h[u]的最大的数
{
    k++;
}
up[k] = h[u]

经过遍历，使得up[]中的数由大到小组成


while(k < sd && h[u] >= down[k])  //找到大于h[u]的第一个最小的数
{
    k++;
}

使得down[]中的数都是小到大组成

C++ 代码

# include <iostream>
using namespace std;

const int N = 55;

int h[N];
int up[N],down[N];

int ans;

int n;

void dfs(int u , int su , int sd)  
{
    if(su + sd >= ans) //目前的情况使用的上升和下降个数和已经大于前面计算的一个方式的最小情况的话，直接return,不用算了
    {
        return;
    }
    if(u == n + 1)
    {
        ans = su + sd;
        return;
    }

    //用上升的物品
    int k = 0;
    while(k < su && h[u] <= up[k])
    {
        k++;
    }
    int temp = up[k];  //用于后面的恢复状态
    up[k] = h[u];
    if(k == su)
    {
        dfs(u + 1 , su + 1 , sd);
    }
    else
    {
        dfs(u + 1 , su , sd);
    }
    up[k] = temp;

    k = 0;
    while(k < sd && h[u] >= down[k])
    {
        k++;
    }
    temp = down[k];
    down[k] = h[u];
    if(k == sd)
    {
        dfs(u + 1 , su , sd + 1);
    }
    else
    {
        dfs(u + 1 , su , sd);
    }
    down[k] = temp;
}

int main()
{
    while(~scanf("%d",&n) && n)
    {
        for(int i = 1 ; i <= n ; i++)
        {
            scanf("%d",&h[i]);
        }

        ans = n;

        dfs(1,0,0);

        printf("%d\n",ans);
    }
    return 0;
}