题目描述

导弹防御系统

dfs暴力深搜上升和下降两种情况

dfs注意边界条件。
深搜过程：
如果全是上升子序列，得到一个ans
如果是上升子序列+一个下降子序列，得到一个ans，更新
。。。。
全是下降子序列，更新ans

#include <iostream>

using namespace std;

const int N=100010;
int a[N],f[N];

int up[N],down[N];

int n;

int ans;
//3个参数分别为：遍历的到第几个数，上升子序列数量，下降子序列数量
void dfs(int u,int su,int sd)
{
    if(su+sd>=ans)
    {
        return;
    }
    if(u==n)
    {
        ans=su+sd;
        return;
    }

    int k=0;
    while(k<su && a[u]<=up[k])
    {
        k++;
    }
    int t=up[k];
    //更新up[k]，即更新这一组的结尾点
    up[k]=a[u];
    if(k<su) dfs(u+1,su,sd);
    else dfs(u+1,su+1,sd);
    up[k]=t;

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

}

int main()
{

    while(cin>>n,n!=0)
    {
    //注意此处不能从1开始
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }

        //初始化res，每次最坏的情况需要n套系统
        ans=n;

        dfs(0,0,0);
        cout<<ans<<endl;

    }

    return 0;
}

2023/11/25

纯dfs + 贪心问题，注释解释的很清楚

#include <iostream>

using namespace std;

const int N=60;
int a[N], f[N];
int n;
int ans;
int up[N], down[N];

// 当前遍历到哪个数， 上升子序列组数，下降子序列组数
void dfs(int u, int su, int sd)
{
    // 如果当前上升组+下降组 已解决超过ans，则返回
    if(su + sd >=ans) return;

    if(u == n)
    {
        ans = su+sd;
        return;
    }


    int k=0;
    while(k<su && a[u]<= up[k])
    {
        k++;
    }
    // 用于恢复现场
    int t = up[k];
    // 找到了第一个 最大的数比a[u]小的上升组
    // 要把该组里最大的数赋成a[u]
    up[k] = a[u];
    // 如果k>su, 说明a[u]比所有上升组的最后一个数(也就是最大的数) 都要小，
    // 说明需要新开一个上升组
    if(k >= su)
    {
        dfs(u+1, su+1, sd);
    }
    else
    {
        dfs(u+1, su, sd);
    }
    // 恢复现场
    up[k] = t;


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


}


int main()
{
    while(cin>>n,n!=0)
    {
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }

        ans = n;

        dfs(0,0,0);

        cout<<ans<<endl;
    }


    return 0;
}