投稿
  1. 首页
  2. C

第一章 动态规划

code • 2022-5-13 • C • 阅读 34

第一章 动态规划,第1张

目录
  • 1、最长上升子序列
  • 2、最长上升子序列 II
  • 3、最长公共子序列
  • 4、最短编辑距离
  • 5、编辑距离
  • 6、怪盗基德的滑翔翼
  • 7、登山
  • 8、合唱队形
  • 9、友好城市
  • 9、补充：不相交的线
  • 10、最大上升子序列和
  • 11、最长上升子序列的个数
  • 12、拦截导d
  • 13、导d防御系统
  • 14、最长公共上升子序列（LIS && LCS）
  • 15、最大整除子集

1、最长上升子序列

ACWing 895

Tips： 子序列 ≠ 子串！KMP用于求子串！

集合

f[i]：所有以第i个数结尾的上升子序列的长度的最大值

集合划分：

状态计算：

f[i] = max(f[i], f[j] + 1), aj < ai, j∈(0, i-1)

#include 
#include 

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1; // 以a[i]结尾的子序列长度为1，只有i一个数
        for (int j = 1; j < i; j ++ ) // 枚举所有i-1位置上的数
            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]);
    
    printf("%d\n", res);
    
    return 0;
}

输出最长上升子序列（倒序）：

#include 
#include 

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];
int g[N]; // 保存每个转移的过程

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1; // 以a[i]结尾的子序列长度为1，只有i一个数
        g[i] = 0; // 表示只有一个数
        
        for (int j = 1; j < i; j ++ ) // 枚举所有i-1位置上的数
            if (a[j] < a[i]) // 保证单调递增
                if (f[i] < f[j] + 1)
                {
                    f[i] = f[j] + 1;
                    g[i] = j; // 记录i从哪个状态(j)转移过来的
                }
    }
    
    int k = 1; // 最优解下标
    for (int i = 1; i <= n; i ++ ) 
        if (f[k] < f[i])
            k = i;
    
    printf("%d\n", f[k]);
    
    for (int i = 0, len = f[k]; i < len; i ++ ) // 输出最长上升子序列（倒序）
    {
        printf("%d ", a[k]);
        k = g[k];
    }
    
    return 0;
}
2、最长上升子序列 II

ACWing 896

优化思路：

假设有一个序列：3 1 2 1 8 5 6

  • 考虑一个性质：
    • 首先考虑长度为1的上升子序列，第一个为3，第二个是1，则在考虑后面所有数的时候，如果它可以添加到3后面构成上升子序列，那么它就一定可以添加到1的后面构成一个上升子序列（因为1比3更小，比如8可以接到3后面构成3 8，那么它一定可以接到1后面构成1 8），所以以3结尾的子序列就没必要存储下来了。总的来说就一句话：考虑一个数接到一个升序的序列后面继续构成升序序列，如果这个数能接到一个结尾更小的序列后面，就一定能接到一个结尾更大的序列后面；
    • 由上面的分析，对于每个长度不同的上升子序列，我们只需要存储每个长度下结尾最小的上升子序列即可。因此我们可以用一个数组记录一下每种长度的上升子序列最后一个元素的值的最小值是多少。并且可以证明随着长度的增加，每种长度的结尾的最小值是单调递增的 ；

    反证法：假设长度为6的上升序列的结尾数值Q6，长度为5的上升序列的结尾数值为Q5，若Q6 <= Q5，因为它们均是单调递增的子序列，所以长度为6的序列的第5个数x一定小于Q6，并且可知x也一定小于Q5，与上面的结论（随着长度的增加，每种长度的结尾的最小值是单调递增的 ）矛盾，故Q6 > Q5，证毕。

  • 由以上性质，对于求任意一个以ai结尾的最长上升子序列的长度，因为ai可以接到任意一个结尾值比它小的上升子序列中，为了求最大值，应该将ai接到以比ai小的数中的最大值结尾的上升序列中。

对于上面最后一点，举个例子详细说明，不然代码中while后面的更新很难理解：

首先，q[i]中存储的是长度为i的单调上升子序列的结尾的最小值。假设有如上图的q，现在我们对任意一个a[i]，通过二分查找，找到了比a[i]小的最大的数a（为什么要最大呢？因为图中的每个长度的单调上升序列的末尾值也是单调的，为了最后得到最长的单调上升子序列，所以应该接到以比a[i]值小的最大的数结尾的单调上升序列后面去，这样就可以保证最后得到的序列长度尽可能地长），且ai可以接到以a结尾的单调上升子序列的末尾中去。这里注意，有关系a < a[i] <= b，如果a[i]插入了以a结尾的单调上升序列中，那么其长度就变成了4，又因为a[i] <= b，所以要对长度为4的子序列末尾进行更新，对应到代码中是q[r + 1] = a[i]，而最大长度的更新就对应代码中的len = max(len, r + 1)，其中的r可以理解为a[i]可以接到长度为r的队列的后面。

Tips：找到小于ai的最大值可以使用二分查找。

整体思路：

对于每一个数a[i]，找到一个以a[i]结尾的最长上升子序列，其长度为len，故最后的len = max(len, 以a[i]结尾的最长上升子序列的长度)。

#include 
#include 

using namespace std;

const int N = 100010;

int n;
int a[N]; // 存储序列
int q[N]; // q[i]表示长度为i的上升子序列结尾的最小值

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    
    int len = 0; // 当前q中的最大长度，即q中的元素个数
    q[0] = -2e9; // 保证数组中小于某个数一定存在，当做哨兵
    for (int i = 0; i < n; i ++ ) // 枚举每个数
    {
        int l = 0, r = len;
        while (l < r) // 在q中二分找出l到r之间 < a[i] 的最大的数
        {
            int mid = l + (r - l + 1) / 2;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        
        len = max(len, r + 1); // r表示可以接在哪个长度的后面，即q中 < a[i] 的最大值的下标（序列长度），接完之后长度要+1
        q[r + 1] = a[i]; // 更新后面一个序列的结尾的值，因为 q[r] < a[i] <= q[r+1]
    }
    
    printf("%d\n", len);
    
    return 0;
}

一点小改变，a的下标从1开始

#include 
#include 

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    
    int len = 0;
    q[0] = -2e9;
    for (int i = 1; i <= n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + (r - l + 1) / 2;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    
    cout << len << endl;
    return 0;
}
3、最长公共子序列

ACWing 897

集合

f[i, j]：所有在第一个序列的前 i 个字母出现，且在第二个序列的前 j 个字母出现的最长公共子序列。

集合划分

  • a[i]、b[j]分别表示两个序列中的第i个元素和第j个元素；
  • 按a[i]、b[j]是否包含在子序列中来划分：
    • 00：a[i]、b[j]均不在f[i,j]中;
    • 01：a[i]在但b[j]不在f[i,j]中;
    • 10：a[i]不在但b[j]在f[i,j]中;
    • 11：a[i]、b[j]均在f[i,j]中。

状态计算：

  • 00：f[i-1,j-1]；
  • 11：f[i-1,j-1] + 1；
  • 01：f[i-1,j]；
  • 10：f[i,j-1]。

对于10和01两种情况的一点解释（解释01，对10的分析同理）：

  • f[i-1,j]表示所有在第一个字符串的前i-1个字符中出现，并且在第二个字符串的前j个字符中出现的一个子序列的最大值——注意关键词”出现“；
  • 01这种情况是表示a[i]不出现在子序列中，b[j]一定出现在子序列中的所有子序列，那么在这种情况下，b[j]就一定是公共序列的结尾——注意关键词”结尾“；
  • 但是在f[i-1,j]出现的子序列并不一定是以b[j]结尾的（因为出现不代表是最后一个字母），因而它们的关系应该是：01 ∈ f[i-1,j]，是一种包含关系！且f[i-1,j]∈f[i,j]。又因为我们最后求的是最大值，所以我们可以用f[i-1,j]来代替01，虽然这样求解最大过程中，可能会有重复的步骤（因为01、10实际上是包含了00这种情况），但是最后的最大值依然不会改变。如果这里是求的数量，那么这里就不能代替了，求数量的子过程是不能重复的！
  • 由以上分析，在实际代码中，00的情况可以不用写；
  • 上面的分析，也说明这LIS与LCS在状态定义上最大的不同。
#include 
#include 

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1); // 涉及i-1和b-1 *** 作，字符串下标最好从1开始
    
    for (int i = 1; i <= n; i ++ ) // 枚举状态
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]); // 计算前面01和10两种情况
            if (a[i] == b[j]) // 如果情况11要成立，且a[i]和b[j]是各自字符串中最后一个，所以它们必须相等
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
        
    printf("%d\n", f[n][m]);
    
    return 0;
}
4、最短编辑距离

ACWing 902

集合

f[i, j]：所有将a[1 ~ i]变成b[1 ~ j]的 *** 作次数的最小值

集合分类：

  • 删掉a[i]之后，a与b匹配，那么要求a[1, i-1]要与b匹配：f[i-1, j] + 1；
  • 增加a[i]之后，a与b匹配，则a[i] = b[j]，那么要求a[1, i-1]与b[1, j-1]匹配：f[i-1, j-1] + 1；
  • 修改a[i]之后，a与b匹配，那么要求a[1, i-1]与b[1, j-1]匹配。如果a[i] == b[j]，则最后不需要+1，否则需要+1：f[i-1, j-1] + (1 or 0)。

状态计算：

f[i, j] = min(f[i-1, j] + 1, f[i-1, j-1] + 1, f[i-1, j-1] + (1 or 0))

#include 
#include 

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);
    
    /* 考虑最初a中没有字符串，要匹配b中的字符串，只有添加 *** 作，添加次数为b的长度 */
    for (int i = 0; i <= m; i ++ ) 
        f[0][i] = i;
    
    /* 考虑最初a中有i个，b中没有字符串，要匹配b中的字符串，只有删除 *** 作，添加次数为a的长度 */    
    for (int i = 0; i <= n; i ++ )
        f[i][0] = i;
        
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            // 前两种情况
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            
            // 第三种情况
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
        
    printf("%d\n", f[n][m]);
    
    return 0;
}
5、编辑距离

ACWing 899

#include 
#include 
#include 

using namespace std;

const int N = 15, M = 1010;

int n, m; // n字符串个数，m询问个数
int f[N][N];
char str[M][N];

// 求出编辑距离
int edit_distance(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1); // 求长度：均从i=1开始计算
    
    for (int i = 0; i <= lb; i ++ ) f[0][i] = i;
    for (int i = 0; i <= la; i ++ ) f[i][0] = i;
    
    for (int i = 1; i <= la; i ++ )
        for (int j = 1; j <= lb; j ++ )
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
        
    return f[la][lb];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%s", str[i] + 1);
    
    while (m -- )
    {
        char s[N];
        int limit;
        scanf("%s%d", s + 1, &limit);
        
        int res = 0;
        for (int i = 0; i < n; i ++ )
            if (edit_distance(str[i], s) <= limit)
                res ++ ;
                
        printf("%d\n", res);
    }
    
    return 0;
}
6、怪盗基德的滑翔翼

ACwing 1017

算法思路： 两遍LIS，正向和反向

#include 
#include 
#include 

using namespace std;

const int N = 110;

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

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        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[i] > a[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        
        memset(f, 0, sizeof f);
        // 这里的两个for循环要注意f[i]的含义来理解
        for (int i = n; i; i -- )
        {
            f[i] = 1; 
            for (int j = n; j > i; j -- )
                if (a[i] > a[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(f[i], res);
        }
        
        cout << res << endl;
    }
    
    return 0;
}
7、登山

ACwing 1014

  • 条件一：按照编号递增的顺序来浏览 ==> 必须是子序列
  • 条件二：相邻两个景点不能相同
  • 条件三：一旦开始下降，就不能上升了==> 先严格单调上升，再严格单调下降
  • 目标：求最多能浏览多少景点 ==> 求出所有形状是上面这种的子序列长度的最大值

集合划分：

按照上图中的尖点在图中什么位置来划分，则有下图

不失一般性，我们求第k类的最大长度。由题意可知，图中尖点左右两边的长度是互不相关的，因此我们只需要使左边长度最大和右边长度最大，最后求和即可。

#include 
#include 

using namespace std;

const int N = 1010;

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

int main()
{
    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[i] > a[j])
                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 (a[i] > a[j])
                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;
}
8、合唱队形

ACWing 482

思路跟上面一道题一样，这道题问至少要剔除多少名同学，也就是要到一个最长的上升下降的子序列。

#include 
#include 

using namespace std;

const int N = 110;

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

int main()
{
    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[i] > a[j])
                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 (a[i] > a[j])
                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;
}
9、友好城市

ACWing 1012

算法思路：

  • 合法的建桥方式：
    • 每个城市上只能建立一座桥；
    • 两桥之间不能相交。
  • 上图两个集合圆中，两个关系是一一对应的。即：每一种合法的建桥方式都对应着一种上升子序列；每一种上升子序列都对应一种合法的建桥方式。
  • 求最多能建多少座桥？也就是先将自变量排序，再按照自变量对应的因变量序列中，寻找最长上升子序即为最多的建桥数量，也就转换成了LIS问题（太妙了！！！）
#include 
#include 

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int n;
PII q[N];
int f[N];

int main()
{
    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[i].second > q[j].second)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    
    cout << res << endl;
    
    return 0;
}
9、补充：不相交的线

LeetCode 1035. 不相交的线

这个题直接就是单纯的LCS问题，与ACwing上的题有点区别。

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<int> a(n + 1), b(m + 1);
        vector<vector<int>> f(n + 1, vector<int>(m + 1));

        for (int i = 0; i < n; i ++ )
            a[i + 1] = nums1[i];
        for (int i = 0; i < m; i ++ )
            b[i + 1] = nums2[i];

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                f[i][j] = max(f[i - 1][j], f[i][j -  1]);
                if (a[i] == b[j])
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        
        return f[n][m];
    }
};
10、最大上升子序列和

ACWing 1016

集合

f[i]：所有以a[i]结尾的上升子序列的和的最大值

集合划分：

状态计算：

f[i] = max(f[i], f[j] + a[i]);

#include 
#include 

using namespace std;

const int N = 1010;

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

int main()
{
    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;
}
11、最长上升子序列的个数

LeetCode 673. 最长递增子序列的个数

需要多使用一个数组g[i]来存储一nums[i]结尾的最长上升子序列的的个数。

  • 每个数都可以独自一个成为子序列，所以起始有g[i] = 1；
  • 对区间[0, i)的所有数nums[j]，如果满足nums[j] < nums[i]，说明nums[i]可以接在nums[j]的后面形成上升子序列，这时候对f[i]和f[j] + 1的大小关系进行讨论：
    • 如果f[i] < f[j] + 1，说明f[i]会被f[j] + 1更新，所以同步更新g[i] = g[j]；
    • 如果f[i] = f[j] + 1，说明找到了一个新的符合条件的前驱，此时将值继续累加到方案数中，即有g[i] += g[j]。

在转移的过程中要记录全局的最长上升子序列的最大长度max，最后结果为所有满足f[i] = max的g[i]的累加值。

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size(), maxLen = 0, ans = 0;
        vector<int> f(n), cnt(n);
        for (int i = 0; i < n; i ++ )
        {
            f[i] = 1, cnt[i] = 1;
            for (int j = 0; j < i; j ++ )
                if (nums[i] > nums[j])
                {
                    if (f[i] < f[j] + 1)
                    {
                        f[i] = f[j] + 1;
                        cnt[i] = cnt[j];
                    }
                    else if (f[i] == f[j] + 1) 
                        cnt[i] += cnt[j];
                }
            if (f[i] > maxLen)
                maxLen = f[i];
        }

        for (int i = 0; i < n; i ++ )
            if (f[i] == maxLen)
                ans += cnt[i];

        return ans;
    }
};

更简洁的写法

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size(), maxLen = 0, ans = 0;
        vector<int> f(n), cnt(n);
        for (int i = 0; i < n; i ++ )
        {
            f[i] = 1, cnt[i] = 1;
            for (int j = 0; j < i; j ++ )
                if (nums[i] > nums[j])
                {
                    if (f[i] < f[j] + 1)
                    {
                        f[i] = f[j] + 1;
                        cnt[i] = cnt[j];
                    }
                    else if (f[i] == f[j] + 1) 
                        cnt[i] += cnt[j];
                }
            
            if (f[i] > maxLen)
            {
                maxLen = f[i];
                ans = cnt[i];
            }
            else if (f[i] == maxLen)
                ans += cnt[i];
        }
        return ans;
    }
};
12、拦截导d

ACWing 1010

第一问就是经典的LIS问题；
第二问思路：

对于样例：389 207 155 300 299 170 158 65。
第一个导d拦截系统由389开头，然后对于207有两种选择。

  • 接在现有的某个子序列后面；
  • 创建一个新的导d系统；

不管上面哪一种选择，将导d207拦截之后，它都是现有的某个子序列的结尾，即可以表示成_____ 207，为了使后面拦截导d后生成的子序列的结尾值尽可能的大，所以对于207应该添加到一个大于等于207的最小的现有子序列后面，如果现有的序列中所有的子序列结尾都小于207，那么我们就创建一个新的子序列。

总的来说：基于贪心思想，从前往后扫描每个数，对于每个数

  • 情况1：如果现有的子序列的结尾都小于当前数，则创建新的子序列
  • 情况2：否则将当前数放到结尾大于等于它的最小的子序列的后面。

思路的证明：如何证明两个数相等？A>=B, B<=A。A表示贪心算法得到的序列个数，B表示最优解，由此必有B<=A。对于A<=B的证明，使用调整法。假设最优解对应的方案和当前方案不同，先找到第一个不同的数，通过交换，将最优解的方案调整成贪心法（因为有n个元素，最多调整n次），且每一次调整并没有增加子序列的个数，所以贪心法得到的最优解的个数是<=最优解的个数，故A<=B，所以能得到最优解。

Tips：
由于本题没有告诉导d的个数，所以在输入的时候要计数。这里使用了两种方法：
方法一： while (cin >> q[n]) n ++ ;
方法二：使用stringstream

#include 

string line;
getline(cin, line);
stringstream ssin(line);
while (ssin >> q[n]) n ++ ;

#include 
#include 

using namespace std;

const int N = 1010;

int n;
int q[N];
int f[N], g[N]; // g存储所有现有的子序列的最后一个数

int main()
{
    while (cin >> q[n]) n ++ ;
    
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (q[j] >= q[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; // k表示从前往后枚举的序列
        while (k < cnt && g[k] < q[i]) k ++ ;
        g[k] = q[i];
        if (k >= cnt) // 如果找不到一个子序列的结尾比小的序列，就开一个新的序列
            cnt ++ ;
    }
    
    cout << cnt << endl;
    
    return 0;
}
13、导d防御系统

ACWing 187

跟上一个题的第二问思路一样，不过要分情况讨论是放到上升子序列还是下降子序列，使用DFS遍历所有情况，ans来记录全局最小值。

#include 
#include 

using namespace std;

const int N = 55;

int n;
int q[N];
int up[N], down[N]; // 分别表示上升子序列和下降子序列的结尾
int ans; // 全局最小值

// u：当前枚举到的第几个数，su：当前上升子序列的个数，sd：当前下降子序列的个数
void dfs(int u, int su, int sd) 
{
    if (su + sd >= ans) // 不可能将ans变小了
        return;
    
    if (u == n) // 找到一种方案
    {
        ans = su + sd;
        return;
    }
    
    // 情况一：将当前数放到上升子序列中
    int k = 0;
    while (k < su && up[k] >= q[u]) k ++ ;
    int t = up[k]; // 备份，因为深搜要回溯恢复现场
    up[k] = q[u];
    if (k < su) // 不开辟一个新的上升子序列
        dfs(u + 1, su, sd);
    else // 开辟一个新的上升子序列
        dfs(u + 1, su + 1, sd);
    up[k] = t; // 恢复现场
    
    // 情况二：将当前数放到下降子序列中
    k = 0;
    while (k < sd && down[k] <= q[u]) k ++ ;
    t = down[k];
    down[k] = q[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)
    {
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
        
        ans = n; // 最坏的情况下有n个防御系统
        dfs(0, 0, 0);
        
        cout << ans << endl;
    }
    
    return 0;
}
14、最长公共上升子序列（LIS && LCS）

ACWing 272

集合
f[i, j]：所有由第一个序列的前i个字母，第二个序列的前j个字母构成的，且以a[i] or b[j]结尾的公共上升子序列

注：这个题目使用的集合是“所有由第一个序列的前i个字母，第二个序列的前j个字母构成的，且以b[j]结尾的公共上升子序列”。

集合划分：

  • 右边：所有不包含a[i]的公共上升子序列，即f[i-1, j]；
  • 左边：所有包含a[i]的公共上升子序列；

对于左边的分析：

按照LIS的划分方法，左边的子序列表示为：
由于左半部分表示的是所有包含a[i]的，且由第一个序列的前i个字母和第二个序列的前j个字母构成的公共上升子序列，现在进一步划分后加上一个限制，即以b[1]结尾，也就包含b序列的前一个字母。所以黄色方框里面所表示的含义为：由第一个序列的前 i 个字母和第二个序列的前 1 个字母构成的，且以b[1]结尾的所有的公共上升子序列。所以左半边的状态表示为f[i, 1] + 1，同理对于以b[k]结尾的状态表示为：f[i, k] + 1，这里的k ∈ [0, j-1]。

朴素版本的代码：

#include 
#include 

using namespace std;

const int N = 3010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
    
    for (int i = 1; i <= n; i ++ )
        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], 1); // 更新左边只有一个数的时候
                for (int k = 1; k < j; k ++ )
                    if (b[k] < b[j]) // 左半边每种情况存在的前提：满足单调上升
                        f[i][j] = max(f[i][j], f[i - 1][k] + 1);
            }
        }
        
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    
    printf("%d\n", res);
    
    return 0;
}

优化代码：对代码做等价变形

  1. 代码第23行，a[i] == b[j]，所以23行后的代码b[j]都可以换成a[i]；
  2. 第一步之后，这个循环的含义发生了变化，
    for (int k = 1; k < j; k ++ )
	if (b[k] < a[i]) 
    	f[i][j] = max(f[i][j], f[i][k] + 1);
    含义是：找到从1到j-1里面小于a[i]的f[i][k]的最大值。因此这个条件与j无关，所以这个循环的含义也就是：在满足某个和j没有关系的条件的前提下，求出其某个前缀[1 ~ j )的最大值。所以可以使用一个变量maxv来记录前缀的最大值，这样可以省掉一层循环。于是第18行开始的代码可以修改为
    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 (b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);
    }
}

最后的代码：

#include 
#include 

using namespace std;

const int N = 3010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &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 (b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    } 
    
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    
    printf("%d\n", res);
    
    return 0;
}
15、最大整除子集

LeetCode 368 最大整除子集

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> f(n, 0), g(n, 0);

        for (int i = 0; i < n; i ++ )
        {
            // 至少包含自身一个数，因此起始长度为 1，由自身转移而来
            int len = 1, prev = i;
            for (int j = 0;j < i; j ++ )
                if (nums[i] % nums[j] == 0)
                	// 如果能接在更长的序列后面，则更新「最大长度」&「从何转移而来」
                    if (f[j] + 1 > len)
                    {
                        len = f[j] + 1;
                        prev = j;
                    }
            // 记录「最终长度」&「从何转移而来」
            f[i] = len;
            g[i] = prev;
        }

		// 遍历所有的 f[i]，取得「最大长度」和「对应下标」
        int idx = 0, manx = -2e9;
        for (int i = 0; i < n; i ++ )
            if (f[i] > manx)
            {
                manx = f[i];
                idx = i;
            }
        int max = f[idx];
        
		// 使用 g[] 数组回溯出具体方案
        vector<int> ans;
        while (ans.size() != max)
        {
            ans.push_back(nums[idx]);
            idx = g[idx];
        }

        return ans;
    }
};

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

原文地址: http://outofmemory.cn/langs/872584.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-05-13
下一篇 2022-05-13

发表评论

登录后才能评论

评论列表（0条）

保存