【学习笔记】线性动态规划1

John_yangliwu · 2021-07-10 22:53:42 · 个人记录

最大子段和

问题引入

给定整数序列 a，求 a 的最大子段和。

思路

首先，一个子段 [l,r] 的和可以写成 sum(r)-sum(l-1) 的形式，其中 sum 为 a 的前缀和数组。

于是考虑枚举 l,r。我们发现，对于一个固定的 r，枚举到的 sum(l-1) 越小，子段 [l,r] 的和就越大。

从 1 开始枚举 r，同时记录使 sum(l-1) 最小的 l，每次用 sum(r)-sum(l-1) 更新答案。

设计一种动态规划，设 dp(i) 表示以 i 为结尾的子段的最大和，则有：

要么接上以 i-1 为结尾的子段，要么以 i 本身为开头成为一个新子段。

进一步简化，对于每个 i，只存储以 i-1 为结尾的子段的最大和为 s，若 s>0，s 就加上 a(i)，反之，使 s=a(i)，然后用 s 更新答案。

例题 1：P1719 最大加权矩形

思路

对每行求前缀和。

枚举左右边界 [l,r]，把边界内的每一行理解成一个整体，第 i 行的和就是 sum(i,r)-sum(i,l-1)，对边界内的整体求最大子段和，更新答案即可。

核心代码

void calc(int l, int r) {
    int s = 0;

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

例题 2：P1121 环状最大两段子段和

思路

分成两个子问题：

1. 求一个非环状序列的最大两段子段和。
2. 求一个环状序列的最大一段子段和。

首先看第一个。

设 dp(i,0) 表示右端点小于等于 i 的子段的最大和，dp(i,1) 表示左端点大于等于 i 的子段的最大和。

用两次对 i 的顺序枚举求 dp(i,0)，两次对 i 的逆序枚举求 dp(i,1) 即可。

最终答案是 \max\limits_{1\le i\le n}\{dp(i,0)+dp(i+1)(1)\}。

对于第二个问题，我们可以思考最优解“长什么样子”。

有两种情况（用 \texttt{x} 表示不选，\texttt{o} 表示选）：

1. \texttt{xxxoooooxxx}
2. \texttt{oooxxxxxooo}

第一种情况直接用最大子段和求解，第二种则是序列总和减去最小子段和，分别求取最大值即可。

然后，把两种情况结合起来，原题的最优解也有两种“样子”：

1. \texttt{xxxooxxooxxx}
2. \texttt{oooxxooxxooo}

第一种便是子问题 1，第二种就是总和减去最小两段子段和。但这里要注意，如果原序列的元素均为负数，不然所有数都会被减掉，在输入后特判即可，答案为最大的两个负数之和。

两种情况类似，都可以用子问题 1 的方法求解，在求第二种前将原序列所有元素改为自己的相反数，可以让程序的改动更少。

核心代码

int calc() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = dp[0][1] = dp[n + 1][0] = dp[n + 1][1] = -2e9;
    for(int i = 1; i <= n; i++) {
        if(dp[i - 1][0] > 0)
            dp[i][0] += dp[i - 1][0];
        dp[i][0] += a[i];  
    }

    for(int i = n; i >= 1; i--) {
        if(dp[i + 1][1] > 0)
            dp[i][1] += dp[i + 1][1];
        dp[i][1] += a[i];
    }

    for(int i = 1; i <= n; i++)
        dp[i][0] = max(dp[i][0], dp[i - 1][0]);
    for(int i = n; i >= 1; i--)
        dp[i][1] = max(dp[i][1], dp[i + 1][1]);

    int ans = -1e9;
    for(int i = 1; i <= n; i++)
        ans = max(ans, dp[i][0] + dp[i + 1][1]);
    return ans;
}

最长上升子序列

问题引入

给出一个长度为 n 整数序列 a，求 a 最长的子序列 g 的长度 m，使得对于所有的 1\le i<m，有 g(i)<g(i+1)。

思路

首先子序列不是子段。

设 dp(i) 为结尾是 a(i) 的最长上升子序列长度，则有：

其中 a(j)<a(i)。

仔细观察发现，每次决策，肯定是选择 dp(j) 最大的 j 的连接上，当有多个这样的 j 时，a(j) 越小，越容易连接上。

所以维护一个数组 g，g(i) 表示长度为 i 的上升子序列的结尾最小值。

对于每个 i，在 g 中查找到大于 a(i) 的最小值 g(j)，j 便是当前的 dp(i)，同时 g(j) 就等于 a(i)。

因为 g 中的元素满足单调性，所以这里的查找可用二分实现。