最长上升子序列模型(LIS)

最长上升子序列

题目链接： https://www.acwing.com/problem/content/897/

状态表示：f[i] 所有以a[i]结尾的严格单调上升子序列最大长度

集合划分：

倒数第二个数可能为：a[1],a[2],……a[i - 1],空

倒数第二个数为空的时候，以a[i]结尾的严格单调上升子序列只有a[i]一个数，因此f[i] = 1

其余情况为：f[i] = f[j] + 1; (1 <= j < i)

求出了以每个数a[i]结尾的严格单调上升子序列的最大长度f[i]后，对所有的f[i]求max，既得最长上升子序列的最大长度

#include <iostream>

using namespace std;

const int N = 1010;
int a[N],f[N];
int main()
{
    int n;
    cin>>n;
    for(int i = 1;i <= n;i++) cin>>a[i];

    for(int i = 1;i <= n;i++)
    {
        f[i] = 1;
        for(int j = 1;j < i;j++)
        {
            if(a[j] < a[i])
            {
                f[i] = max(f[i],f[j] + 1);
            }
        }
    }

    int res = 0;

    for(int i = 1;i <= n;i++)
    {
        res = max(res,f[i]);
    }

    cout<<res<<endl;
    return 0;
}

怪盗基德的滑翔翼

题目链接： https://www.acwing.com/problem/content/1019/

思路：按顺序排列的数组，只能选择一个方向，按照从高到底，求一个最长严格单调下降子序列，从左往右求一遍，然后再从右往左求一遍，对所有的f[i]求max。

#include <iostream>

using namespace std;
const int N = 110;
int a[N],f[N];

int main()
{
    int k;
    cin>>k;
    while(k--)
    {
        int n;
        cin>>n;
        for(int i = 1;i <= n;i++) cin>>a[i];

        int res = 0;
        for(int i = 1;i <= n;i++)
        {
            f[i] = 1;
            for(int j = 1;j < i;j++)
            {
                if(a[j] > a[i])
                {
                    f[i] = max(f[i],f[j] + 1);
                }
            }
            res = max(res,f[i]);
        }

        for(int i = n;i >= 1;i--)
        {
            f[i] = 1;
            for(int j = n;j > i;j--)
            {
                if(a[j] > a[i])
                {
                    f[i] = max(f[i],f[j] + 1);
                }
            }
            res = max(res,f[i]);
        }

        cout<<res<<endl;
    }
    return 0;
}

登山

题目链接： https://www.acwing.com/problem/content/1016/

思路：

“一旦开始下山，就不再向上走了”提示我们，这个题目求得的是一个，先严格单调上升再严格单调下降的子序列。

以a[k]为中间节点，先求从左往右以a[k]结尾的最长上升子序列 l[i]，再求从右往左以a[k]结尾的最长上升子序列 r[i]，

两边的最大长度相加 - 1，就是这个先上升再下降的子序列的最大长度。

#include <iostream>

using namespace std;
const int N = 1010;

int a[N],l[N],r[N];

int main()
{
    int n;
    cin>>n;

    for(int i = 1;i <= n;i++) cin>>a[i];

    for(int i = 1;i <= n;i++)
    {
        l[i] = 1;
        for(int j = 1;j < i;j++)
        {
            if(a[j] < a[i]) l[i] = max(l[i],l[j] + 1);
        }
    }

    for(int i = n;i >= 1;i--)
    {
        r[i] = 1;
        for(int j = n;j > i;j--)
        {
            if(a[j] < a[i]) r[i] = max(r[i],r[j] + 1);
        }
    }

    int res = 0;
    for(int i = 1;i <= n;i++) res = max(res,l[i] + r[i] - 1);

    cout<<res<<endl;
    return 0;
}

合唱队形

题目链接： https://www.acwing.com/problem/content/484/

思路：同登山先上升再下降，与登山不同的是，1-----a[k] a[k + 1]------a[n],因此最大长度为l[i] + r[k]取max。

#include <iostream>

using namespace std;

const int N = 110;

int a[N],l[N],r[N];
int main()
{
    int n;
    cin>>n;

    for(int i = 1;i <= n;i++) cin>>a[i];

    for(int i = 1;i <= n;i++)
    {
        l[i] = 1;
        for(int j = 1;j < i;j++)
        {
            if(a[j] < a[i])
            {
                l[i] = max(l[i],l[j] + 1);
            }
        }
    }

    for(int i = n;i >= 1;i--)
    {
        for(int j = n;j > i;j--)
        {
            if(a[j] < a[i])
            {
                r[i] = max(r[i],r[j] + 1);
            }
        }
    }

    int res = 0;
    for(int i = 1;i <= n;i++)
    {
        res = max(res,l[i] + r[i]);
    }

    cout<<n - res<<endl;
    return 0;
}

友好城市

题目链接： https://www.acwing.com/problem/content/1014/

思路：输入的是每一对南北岸友好城市的坐标，乱序，所以按照一岸的点由小到大排好序，会发现，另一岸的点满足最长上升子序列模型时，所连接的友好城市才不相交！

排序写题经常用！

#include <iostream>
#include <algorithm>

using namespace std;
typedef pair<int,int> PII;

const int N = 5010;
PII q[N];
int f[N];
int main()
{
    int n;
    cin>>n;

    for(int i = 0;i < n;i++) cin>>q[i].first>>q[i].second;

    sort(q,q + n);

    int res = 0;
    for(int i = 0;i < n;i++)
    {
        f[i] = 1;
        for(int j = 0;j < i;j++)
        {
            if(q[j].second < q[i].second)
            {
                f[i] = max(f[i],f[j] + 1);
            }
        }
        res = max(res,f[i]);
    }

    cout<<res<<endl;
    return 0; 
}

最大上升子序列和

题目链接： https://www.acwing.com/problem/content/1018/

思路：

类比最大上升子序列模型，最大上升子序列求的是子序列的最大长度，而此题要求求最大上升子序列的和，类比最大上升子序列模型的分析过程，我们重新分析一遍：

状态表示：f[i] 所有以a[i]结尾的严格单调上升子序列最大和

集合划分：

倒数第二个数可能为：a[1],a[2],……a[i - 1],空

倒数第二个数为空的时候，以a[i]结尾的严格单调上升子序列只有a[i]一个数，因此f[i] = a[i]

其余情况为：f[i] = f[j] + a[i]; (1 <= j < i)

求出了以每个数a[i]结尾的严格单调上升子序列的最大和f[i]后，对所有的f[i]求max，既得最长上升子序列的最大和

#include <iostream>

using namespace std;
const int N = 1010;

int a[N],f[N];

int main()
{
    int n;
    cin>>n;

    for(int i = 1;i <= n;i++) cin>>a[i];

    int res = 0;
    for(int i = 1;i <= n;i++)
    {
        f[i] = a[i];
        for(int j = 1;j < i;j++)
        {
            if(a[j] < a[i])
            {
                f[i] = max(f[i],f[j] + a[i]);
            }
        }
        res = max(res,f[i]);
    }

    cout<<res<<endl;
    return 0;
}

拦截导弹（贪心）

题目链接： https://www.acwing.com/problem/content/1012/

题目要求求一个严格单调不上升子序列

贪心流程：

从前往后扫描每个数，对于每个数：

​ ①：如果现有的子序列的结尾都小于当前数，则创建新子序列（如果对所有的子序列不满足“严格单调不上升”的性质，则创建新的子序列）

​ ②：将当前数放到结尾大于等于它的最小的子序列后面（对于每个序列的每个数满足严格单调不上升）

贪心证明：

1、如何证明两个数相等？A >= B,A <= B

​ A:表示贪心算法得到的序列个数

​ B:表示最优解

因为B是最优解，所以有：

• ​ B <= A

我们接下来证明A <= B（调整法）:

假设最优解对应的方案和当前贪心的方案不同，因此我们就可以找的到第一个不同的数：

贪心法得到a是大于x的最小的数：以a结尾的子序列

​ ---------⚪⚪

​ a x

最优解得到b是大于x的数(仅为x的前面的数，并不是最小的数)：以b结尾的子序列

​ ---------⚪⚪

​ b x

因为贪心得到的a是大于x的最小的数，而最优解得到的b仅是x的前面的数，所以，b >= a

我们补齐x后面的序列：

---------⚪⚪-------- ①

​ a x

---------⚪⚪-------- ②

​ b x

由于a >= x:

​ 所以②中的x后面的序列可以换到a的后面

由于b >= a:

​ 所以①中的x后面的序列也可以换到b的后面

发现两个序列是可以交换的，并且交换之后是合法还没有增加序列的个数，由于子序列长度是有限的，所以我们的调整次数最多可以调整n次，就可以把最优解调整成贪心法，并且每一次调整都没有增加子序列的个数，所以贪心法得到的序列个数是小于等于最优解得到的序列个数。

• A <= B

#include <iostream>

using namespace std;
const int N = 1010;

int a[N],f[N],g[N];

int n;

int main()
{
    while(cin>>a[n]) n++;

    int res = 0;
    for(int i = 0;i < n;i++) 
    {
        f[i] = 1;
        for(int j = 0;j < i;j++)
        {
            if(a[j] >= a[i])
            {
                f[i] = max(f[i],f[j] + 1);
            }
        }
        res = max(res,f[i]);
    }

    cout<<res<<endl;

    int cnt = 0;//序列的数量，一开始序列的数量为零
    for(int i = 0;i < n;i++)
    {
        int k = 0;//序列的索引
        while(k < cnt && g[k] < a[i]) k++;//当序列的索引在范围之内且该序列的结尾比当前数小的话，就k++寻找下一个序列
        g[k] = a[i];//当该序列的结尾大于等于当前数的话或者遍历完所有序列都没有当前序列的结尾大于等于当前数的序列，就创造一个新的序列
        if(k >= cnt) cnt++;//判断这个序列的索引是否超出范围，是的话，创造一个新的序列，使cnt++
    }

    cout<<cnt<<endl;
    return 0;
}

导弹防御系统（贪心 + dfs)

题目链接： https://www.acwing.com/problem/content/189/

建议看这道题前先复习一下此题：拦截导弹

通过dfs爆搜的方式来枚举：

为什么不用bfs而用dfs：

bfs搜索全局，容易爆栈，然而dfs可以通过剪枝来缩小搜索空间

具体看注释：

#include <iostream>

using namespace std;

const int N = 55;

int a[N];
int up[N],down[N];
int ans,n;

/*

u：表示枚举到了第几个导弹，枚举所有导弹

su：严格单调上升的子序列的个数

sd：严格单调下降的子序列的个数
*/
void dfs(int u,int su,int sd)
{
    if(su + sd >= ans) return;//如果两个上升和下降的子序列个数加起来超过了最坏情况，说明答案ans不可能再变小了。

    if(u == n)//枚举完所有的数
    {
        ans = sd + su;//答案是sd + su
        return;
    }

    //情况一，严格单调上升子序列
    int k = 0;
    while(k < su && up[k] >= a[u]) k++;//若子序列不满足严格单调上升，就寻找下一个已存在序列
    int t = up[k];//保存现场，以便恢复
    up[k] = a[u];//找到当前子序列的结尾的数小于当前的数或者所有序列没有满足前者则创造一个新序列
    if(k < su) dfs(u + 1,su,sd);//若未创造一个新序列
    else dfs(u + 1,su + 1,sd);//创造一个新序列，su的数量加一
    up[k] = t;//恢复现场

    //情况二，严格单调下降子序列
    k = 0;
    while(k < sd && down[k] <= a[u]) k++;//若子序列不满足严格单调下降，就寻找下一个已存在序列
    t = down[k];
    down[k] = a[u];//找到当前子序列的结尾的数大于当前的数或者所有序列没有满足前者则创造一个新序列
    if(k < sd) dfs(u + 1,su,sd);
    else dfs(u + 1,su,sd + 1);//创造一个新序列，sd的数量加一
    down[k] = t;
}
int main()
{
    while(cin>>n,n)
    {
        for(int i = 0;i < n;i++) cin>>a[i];

        ans = n;//最坏情况，需要n个导弹系统覆盖n个导弹

        dfs(0,0,0);

        cout<<ans<<endl;
    }
    return 0;
}

最长公共上升子序列

题目链接： https://www.acwing.com/problem/content/274/

题解且看y总：

https://www.acwing.com/solution/content/4955/