概述

线性动态规划，是较常见的一类动态规划问题，其是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板。

线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值。

因此，除了少量问题（如LIS、LCS、LCIS等）有固定的模板外，大部分都要根据实际问题来推导得出答案。

典型题目

LIS

线性dp

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        for (int i = 1; i < dp.size(); i++)
            for (int j = 0; j < i; j++)
                if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
        return *max_element(dp.begin(), dp.end());
    }
};

贪心+二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> d;
        for (auto x : nums) {
            if (d.empty() || x > d.back()) d.emplace_back(x);
            else {
                int index = lower_bound(d.begin(), d.end(), x) - d.begin();
                d[index] = x;
            }
        }
        return d.size();
    }
};

LCS1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int longestCommonSubsequence(string& text1, string& text2) {
        vector <vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1));
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp.back().back();
    }
};

LCS2

关于为什么可以转化成LIS问题，这里提供一个解释。

A:3 2 1 4 5

B:1 2 3 4 5

我们不妨给它们重新标个号：把3标成a,把2标成b，把1标成c … 于是变成：

A: a b c d e

B: c b a d e

这样标号之后，LCS长度显然不会改变。但是出现了一个性质：

两个序列的子序列，一定是A的子序列。而A本身就是单调递增的。因此这个子序列是单调递增的。

换句话说，只要这个子序列在B中单调递增，它就是A的子序列。哪个最长呢？当然是B的LIS最长。自此完成转化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
std::ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> arr1(n), arr2(n);
for (int i = 0; i < n; i++) cin >> arr1[i];
for (int i = 0; i < n; i++) cin >> arr2[i];
vector<int> arr3(n);
unordered_map<int, int> map;
int number = 1;
for (auto& x : arr1)
    map[x] = number++;
for (auto& x : arr2)
    x = map[x];
vector<int> d;
for (auto x : arr2) {
    if (d.empty() || x > d.back()) d.emplace_back(x);
    else {
        int index = lower_bound(d.begin(), d.end(), x) - d.begin();
        d[index] = x;
    }
}
cout << d.size() << endl;

导弹拦截

Dilworth 定理: 对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int maxN = 1e5 + 5;
int N = 0;
int arr[maxN];

int main() {
    while (cin >> arr[N]) N++;
    vector<int> d;
    for (int i = 0; i < N; i++) {
        if (d.empty() || d.back() >= arr[i]) d.emplace_back(arr[i]);
        else {
            int index = upper_bound(d.begin(), d.end(), arr[i], greater())
                        - d.begin();
            d[index] = arr[i];
        }
    }
    cout << d.size() << endl;
    vector<int> p;
    for (int i = 0; i < N; i++) {
        if (p.empty() || p.back() < arr[i]) p.emplace_back(arr[i]);
        else {
            int index = lower_bound(p.begin(), p.end(), arr[i]) - p.begin();
            p[index] = arr[i];
        }
    }
    cout << p.size() << endl;
}

回文字串

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string str;

int dp[1005][1005];

int main() {
    std::ios::sync_with_stdio(false);
    cin >> str;
    memset(dp, 0, sizeof(dp));
    for (int k = 1; k < str.size(); k++) {
        for (int i = 0; i + k < str.size(); i++) {
            int j = i + k;
            if (str[i] == str[j]) dp[i][j] = dp[i + 1][j - 1];
            else dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
        }
    }
    cout << dp[0][str.size() - 1] << endl;
}

解法二

该题说是考察如何将一个字符串添加成一个回文串的，不如说是一道求最长公共自序列的变式题，为啥这么说呢？肯定是有原因在里面的。

首先，我们要摸清回文串的特性，回文就是正着读反着读一样，一种非常对称不会逼死强迫症的字符串；这就是我们的突破口。你难道以为是逼死强迫症么？哈哈，太天真了，突破口其实是因为回文正着读反着读都相同的特性。这样我们就可以再建一个字符数组存储倒序的字符串。

先分析样例：ab3bd

它的倒序是: db3ba

这样我们就可以把问题转化成了求最长公共自序列的问题，为啥可以这么转化呢？

它可以这么理解，正序与倒序“公共”的部分就是我们回文的部分，如果把正序与倒序公共的部分减去你就会惊奇的发现剩余的字符就是你所要添加的字符，也就是所求的正解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string str1;
int dp[1005][1005];

int main() {
    std::ios::sync_with_stdio(false);
    cin >> str1;
    string str2;
    for (int i = str1.size() - 1; i >= 0; i--) str2.push_back(str1[i]);
    for (int i = 1; i <= str1.size(); i++) {
        for (int j = 1; j <= str2.size(); j++) {
            if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    cout << str1.size() - dp[str1.size()][str2.size()] << endl;
}

乌龟棋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int N, M;
int score[355];
int card[5];
int dp[45][45][45][45];

int main() {
    cin >> N >> M;
    memset(score, 0, sizeof(score));
    memset(card, 0, sizeof(card));
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < N; i++) cin >> score[i];
    for (int i = 0; i < M; i++) {
        int temp;
        cin >> temp;
        card[temp]++;
    }
    dp[0][0][0][0] = score[0];
    for (int i = 0; i <= card[1]; i++) {
        for (int j = 0; j <= card[2]; j++) {
            for (int k = 0; k <= card[3]; k++) {
                for (int t = 0; t <= card[4]; t++) {
                    int index = i + j * 2 + k * 3 + t * 4;
                    if (i > 0)
                        dp[i][j][k][t] = max(dp[i][j][k][t], dp[i - 1][j][k][t] + score[index]);
                    if (j > 0)
                        dp[i][j][k][t] = max(dp[i][j][k][t], dp[i][j - 1][k][t] + score[index]);
                    if (k > 0)
                        dp[i][j][k][t] = max(dp[i][j][k][t], dp[i][j][k - 1][t] + score[index]);
                    if (t > 0)
                        dp[i][j][k][t] = max(dp[i][j][k][t], dp[i][j][k][t - 1] + score[index]);
                }
            }
        }
    }
    int ans = dp[card[1]][card[2]][card[3]][card[4]];
    cout << ans << endl;
}

Negatives and Positives

线性dp+状态记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int maxN = 2e5 + 5;

long long arr[maxN];
long long dp[2][maxN];//两个状态

int main() {
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int size;
        cin >> size;
        for (int i = 0; i < size; i++) cin >> arr[i];
        dp[0][0] = arr[0];
        dp[1][0] = -arr[0];
        for (int i = 1; i < size; i++) {
            dp[0][i] = max(dp[0][i - 1] + arr[i], dp[1][i - 1] - arr[i]);
            dp[1][i] = max(dp[0][i - 1] - arr[i], dp[1][i - 1] + arr[i]);
        }
        cout << dp[0][size - 1] << endl;
    }
}

排序+数学归纳

由题意易知我们可以将任意两个数都进行取相反数, 这里不做证明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int maxN = 2e5 + 5;

long long arr[maxN];

int main() {
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int size;
        cin >> size;
        long long ans = 0;
        for (int i = 0; i < size; i++) cin >> arr[i], ans += arr[i];
        sort(arr, arr + size);
        for (int i = 0; i < size - 1; i += 2) {
            if (arr[i] + arr[i + 1] < 0) {
                ans = ans + 2 * (-arr[i] - arr[i + 1]);
            }
        }
        cout << ans << endl;
    }
}

Save the Magazines

线性dp+状态记录

定义状态f(i,0)和f(i,1)，其中f(i,0)表示所有将前i个箱子的盖子移动完且第i个箱子没有使用第i+1个箱子的盖子的所有方案，f(i,1)表示所有将前i个箱子的盖子移动完且第i个箱子使用第i+1个箱子的盖子的所有方案。属性就是保护的杂志的最大数量。

状态转移方程需要分类讨论：

  1. 第i个箱子原本没有盖子，且第i+1个箱子也没有盖子，那么有f(i,0)=f(i−1,0)。
  2. 第i个箱子原本有盖子，且第i+1个箱子没有盖子，那么有f(i,0)=max{f(i−1,0)+ai,f(i−1,1)}。
  3. 第i个箱子原本没有盖子，且第i+1个箱子有盖子，那么有f(i,0)=f(i−1,0),f(i,1)=f(i−1,0)+ai。
  4. 第i个箱子原本有盖子，且第i+1个箱子有盖子，那么有f(i,0)=max{f(i−1,0)+ai,f(i−1,1)}, f(i,1)=f(i−1,1)+ai。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int maxN = 2e5 + 5;
int dp[maxN][2];
char str[maxN];
int arr[maxN];

int main() {
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 0;
        int n;
        cin >> n;
        cin >> (str + 1);
        for (int i = 1; i <= n; i++) cin >> arr[i];
        for (int i = 1; i <= n; i++) {
            if (str[i] == '0') {
                dp[i][0] = dp[i - 1][0];
                if (str[i + 1] == '1') {
                    dp[i][1] = dp[i - 1][0] + arr[i];
                }
            } else {
                dp[i][0] = max(dp[i - 1][1], dp[i - 1][0] + arr[i]);
                if (str[i + 1] == '1') {
                    dp[i][1] = dp[i - 1][1] + arr[i];
                }
            }
        }
        cout << dp[n][0] << endl;
    }
}

贪心

我们将s序列分成若干段，每一段的形式都是第一个数是0，后面都是连续的1（可能只有一个0而没有1）。如果s[0]不为0，那么第一段就只包含连续的1。比如有111010011，那么按照这个规则s划分成如下形式：[111] [01] [0] [011]。

为什么会想到这样子划分呢？因为根据题目的信息，每个盖子只能被移动一次，这样划分就可以保证每一段之间都是相互独立的，因为每一段的第一个位置为0（第一段除外），因此如果这个0被这一段后面的盖子覆盖后，由于这个盖子已经移动过一次了，因此不可能再往前移动，因此每一段都是互不影响的。

因此要求出所有箱子能保护的杂志最大数量，等价于求每一段中能够保存的杂志最大数量。可以发现对于 0 1 1 ... 1 这种形式，通过往前移动盖子我们可以让0出现在任意一个位置，因此要使得这段中能保护的杂志数量最大，就是累加这一段中所有箱子存放的杂志数量，再减去存放最小杂志数量的箱子所存放的杂志（也就是说把0变到存放杂志数量最少的箱子上）。

为了方便，一开始就给序列s头插一个0，保证s[0]=0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int maxN = 2e5 + 5;
char str[maxN];
int arr[maxN];

int main() {
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n >> (str + 1);
        str[0] = '0', arr[0] = 0;
        for (int i = 1; i <= n; i++) cin >> arr[i];
        int ans = 0;
        for (int i = 0; i <= n; i++) {
            if (str[i] == '0') {
                int sum = arr[i], min = arr[i];
                int j = i + 1;
                while (j <= n && str[j] == '1') {
                    min = std::min(min, arr[j]);
                    sum += arr[j];
                    j++;
                }
                ans += sum - min;
                i = j - 1;
            }
        }
        cout << ans << endl;
    }
}