投稿
  1. 首页
  2. 随笔

动态规划--最长上升子序列模型

挂起状态 • 2022-12-16 • 随笔 • 阅读 54

动态规划--最长上升子序列模型,第1张

动态规划--最长上升子序列模型

文章目录
  • 一、前言
  • 二、AcWing 1017. 怪盗基德的滑翔翼
    • 1.题目
    • 2.逻辑解释
    • 3.AC代码
  • 三、AcWing 1014. 登山
    • 1.题目
    • 2.逻辑解释
    • 3.AC代码
  • 四、AcWing 482. 合唱队形
    • 1.题目
    • 2.逻辑解释
    • 3.AC代码
  • 五、AcWing 1012. 友好城市
    • 1.题目
    • 2.逻辑解释
    • 3.AC代码
  • 六、AcWing 1016. 最大上升子序列和
    • 1.题目
    • 2.逻辑解释
    • 3.AC代码
  • 七、AcWing 1010. 拦截导d
    • 1.题目
    • 2.逻辑解释
    • 3.AC代码
  • 八、AcWing 187. 导d防御系统
    • 1.题目
    • 2.逻辑解释
    • 3.AC代码
  • 九、AcWing 272. 最长公共上升子序列
    • 1.题目
    • 2.AC代码
  • 十、额外的练习题

一、前言

AcWing算法提高课内容，本文讲解 动态规划

本篇包括以下题目：

⭐️AcWing 1017. 怪盗基德的滑翔翼
⭐️AcWing 1014. 登山
⭐️AcWing 1017. AcWing 1012. 友好城市
⭐️AcWing 1017. AcWing 1016. 最大上升子序列和
⭐️AcWing 1017. AcWing 1010. 拦截导d
⭐️AcWing 1017. AcWing 187. 导d防御系统
⭐️AcWing 1017. AcWing 272. 最长公共上升子序列

写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来，博主会立即改正！望大家海涵

文末附有几道练习题目，读者在看懂上述题目之后可以拿来练手，题目链接为本人博客(博客中有原题链接)，每道题目均附有题解。

本文需要先自修基础：线性DP

二、AcWing 1017. 怪盗基德的滑翔翼 1.题目

本题链接：怪盗基德的滑翔翼
本博客提供本题截图：

2.逻辑解释

我们把题目抽象一下，其实就是要求一个最长下降子序列，因为题目中说基德可以在任意一个房子的屋顶，所以我们只需要从左往右飞一遍，再从右往左飞一遍，两遍去最大值即可.

3.AC代码 
#include 
#include 

using namespace std;

const int N = 110;

int h[N], f[N];

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        int n;
        cin >> n;
        for (int i = 0; i < n; i ++ ) cin >> h[i];
        
        int res = 0;
        for (int i = 0; i < n; i ++ )    //n个房子依次遍历，往左飞
        {
            f[i] = 1;
            for (int j = 0; j < i; j ++ ) 
                if (h[j] < h[i])
                    f[i] = max(f[i], f[j] + 1);
            
            res = max(res, f[i]);
        }
        
        for (int i = n - 1; ~i; i -- )   //n个房子依次遍历，往右飞
        {
            f[i] = 1;
            for (int j = n - 1; j > i; j -- ) 
                if (h[j] < h[i])
                    f[i] = max(f[i], f[j] + 1);
                    
            res = max(res, f[i]);
        }
        
        cout << res << endl;
    }
    
    return 0;
}
三、AcWing 1014. 登山 1.题目

本题链接：登山
本博客提供本题截图：

2.逻辑解释

题目抽象后，本题其实就是求一个先上升再下降的序列的最大值，和上题思路其实一致，先做一次最长上升子序列f[i]再做一次最长下降子序列g[i]，最后按照第 i个点分开求 max(f[i] + g[i] - 1)

3.AC代码 
#include 
#include 

using namespace std;

const int N = 1010;

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

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    
    for (int i = 1; i <= n; i ++) 
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ ) 
            if (h[j] < h[i]) 
                f[i] = max(f[i], f[j] + 1);
    }
    for (int i = n; i; i -- )
    {
        g[i] = 1;
        for (int j = n; j > i; j -- ) 
            if (h[j] < h[i])
                g[i] = max(g[i], g[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = max(res, f[i] + g[i] - 1);
        
    cout << res << endl;
    
    return 0;
}
四、AcWing 482. 合唱队形 1.题目

本题链接：合唱队形
本博客提供本题截图：

2.逻辑解释

看成一个上升子序列 + 一个下降子序列，f[i]表示以i为结尾的最长上升子序列，g[i]表示以i为开头的最长下降自序列，本题问最少需要几名同学出列，其实就是问出列后队伍最长是多长，即我们需要求一个上升子序列和一个下降子序列，使得这两个子序列的长度和最长，即求max(f[i] + g[i] - 1)，-1的原因是因为i这个位置算了两次，然后就变成了一个简单的 LIS问题.

3.AC代码 
#include 
#include 

using namespace std;

const int N = 110;

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

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    
    for (int i = 1; i <= n; i ++ ) 
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ ) 
            if (h[j] < h[i])
                f[i] = max(f[i], f[j] + 1);
    }
    
    for (int i = n; i; i -- )
    {
        g[i] = 1;
        for (int j = n; j > i; j -- )
            if (h[j] < h[i])
                g[i] = max(g[i], g[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = max(res, f[i] + g[i] - 1);
        
    cout << n - res << endl;
    
    return 0;
}
五、AcWing 1012. 友好城市 1.题目

本题链接：友好城市
本博客提供本题截图：

2.逻辑解释

本题就是造桥，每个桥有两个参数x1和x2，表示桥的一头连接在上岸坐标为x1的地方，一头连在下岸坐标为x2的地方，我们所求的为在要求桥不想交的前提下，建尽可能多的桥

以上图一中红色的就是题目中的样例，图二中蓝色的则是我们最后选择的桥梁。
我们可以按照上岸的坐标从小到大来枚举，然后我们只需关心下岸的坐标之间有何关系即可；于是，不难发现，上坐标从小到大枚举选择到的桥，其对应下坐标也必然是从小到大的.

3.AC代码 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair PII;

const int N = 5010;

PII h[N];
int f[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> h[i].x >> h[i].y;
    
    sort(h, h + n);
    
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < n; j ++ ) 
            if (h[j].y < h[i].y)
                f[i] = max(f[i], f[j] + 1);
                
        res = max(res, f[i]);
    }
    
    cout << res << endl;
    
    return 0;
}
六、AcWing 1016. 最大上升子序列和 1.题目

本题链接：最大上升子序列和
本博客提供本题截图：

2.逻辑解释

这是一个裸题，不需要我们对内容进行抽象，状态表示：f[i] 表示前i个数中的最大子序列和；状态转移：if (a[j] < a[i]) f[i] = max(f[i], f[j] + a[i])

3.AC代码 
#include 
#include 

using namespace std;

const int N = 1010;

int a[N], f[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    
    int res = 0;
    for (int i = 0; i < n; i ++ ) 
    {
        f[i] = a[i];
        for (int j = 0; 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;
}
七、AcWing 1010. 拦截导d 1.题目

本题链接：拦截导d
本博客提供本题截图：

2.逻辑解释

f数组表示的是在前 i个导d中的最长不上升子序列的长度，最后对所有的 f[i] 取一个最大值即可
g数组存储的是每一个防伪系统中的结尾导d高度，对于每一个 h 数组中的元素，我们都会有两种选择，开一个新的防卫系统，或者是接到某一个系统的结尾

3.AC代码 
#include 
#include 

using namespace std;

const int N = 100010;

int f[N];  //f数组存储的是最长不上升序列（注意不是子序列） 
int g[N];  //g数组存储的是最长上升序列（注意不是子序列）
int h[N];
int n;

int main() 
{
	while (cin >> h[++ n]);
	n --;
	
	int res = 1, cnt = 1;
	f[1] = g[1] = h[1];
	for (int i = 2; i <= n; i ++ ) 
	{
		if (h[i] <= f[res]) f[++ res] = h[i];
		else
		{
			int k = upper_bound(f + 1, f + res + 1, h[i], greater()) - f;
			f[k] = h[i];
		}
		
		if (h[i] > g[cnt]) g[++ cnt] = h[i];
		else
		{
			int k = lower_bound(g + 1, g + cnt + 1, h[i]) - g;
			g[k] = h[i];
		}
	}
	
	printf("%dn%dn", res, cnt);
	
	return 0;
}
八、AcWing 187. 导d防御系统 1.题目

本题链接：导d防御系统
本博客提供本题截图：

2.逻辑解释

用up[k]和down[k]记录第k套上升（下降）系统目前所拦截的最后一个导d，dfs(u,v,t)意味着已有u个上升，v个下降，正在处理第t个数，这里还涉及到一个贪心的思路：假设现在要把一个数放入一个上升序列，那么一定是所有能放入的上升序列中，最后一个元素最大的那一个.

3.AC代码 
#include 
#include 

using namespace std;

const int N = 55;

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

void dfs(int u, int su, int sd)
{
    if (su + sd >= res) return;
    if (u == n)
    {
        res = su + sd;
        return;
    }
    
    int k = 0;
    while (k < su && up[k] >= h[u]) k ++;
    int t = up[k];
    up[k] = h[u];
    if (k >= su) dfs(u + 1, su + 1, sd);
    else dfs(u + 1, su, sd);
    up[k] = t;
    
    k = 0;
    while (k < sd && down[k] <= h[u]) k ++;
    t = down[k];
    down[k] = h[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)
    {
        for (int i = 0; i < n; i ++ ) cin >> h[i];
        res = n;
        dfs(0, 0, 0);
        cout << res << endl;
    }
    
    return 0;
}
九、AcWing 272. 最长公共上升子序列 1.题目

本题链接：最长公共上升子序列
本博客提供本题截图：

2.AC代码 
#include 
#include 

using namespace std;

const int N = 3010;

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

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

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

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    cout << res << endl;

    return 0;
}
十、额外的练习题

P1020 [NOIP1999 普及组] 导d拦截
P1439 【模板】最长公共子序列
P1280 尼克的任务
P2758 编辑距离
P4933 大师
P1077 [NOIP2012 普及组] 摆花
P1233 木棍加工

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5670157.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
挂起状态 挂起状态 一级用户组
0 0
上一篇 2022-12-16
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存