线性DP

P1091 合唱队形

依次求出每个数字前面和后面分别的最长上升/下降子序列

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), f(n + 1, 1), g(n + 1, 1);
    for (int i = 1; i <= n;i++)cin >> a[i];
    for (int i = n - 1;i >= 1;i--) {
        for (int j = i + 1;j <= n;j++) {
            if (a[i] > a[j])f[i] = max(f[i], f[j] + 1);
        }
    }
    for (int i = 2;i <= n; i++) {
        for (int j = 1;j < i;j++) {
            if (a[i] > a[j])g[i] = max(g[i], g[j] + 1);
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        ans = max(ans, f[i] + g[i] - 1);
    }
    cout << n - ans << '\n';
}

P1095 守望者的逃离

void solve() {
    int m, s, t;cin >> m >> s >> t;
    vector<int> dp(t + 1);
    for (int i = 1;i <= t;i++) {
        if (m >= 10) {
            dp[i] = dp[i - 1] + 60;m -= 10;
        } else {
            dp[i] = dp[i - 1];m += 4;
        }
    }
    for (int i = 1;i <= t;i++) {
        dp[i] = max(dp[i], dp[i - 1] + 17);
        if (dp[i] >= s) {
            cout << "Yes\n";cout << i << "\n";return;
        }
    }
    cout << "No\n";cout << dp[t] << '\n';
}

P1541 乌龟棋

4 维 DP

int f[45][45][45][45];
void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int num[5] = {};
    for (int i = 1;i <= m;i++) {
        int x;cin >> x;num[x]++;
    }
    f[0][0][0][0] = a[1];
    for (int i = 0;i <= num[1];i++) {
        for (int j = 0;j <= num[2];j++) {
            for (int k = 0;k <= num[3];k++) {
                for (int p = 0;p <= num[4];p++) {
                    int r = 1 + i + 2 * j + 3 * k + 4 * p;
                    if (i)f[i][j][k][p] = max(f[i][j][k][p], f[i - 1][j][k][p] + a[r]);
                    if (j)f[i][j][k][p] = max(f[i][j][k][p], f[i][j - 1][k][p] + a[r]);
                    if (k)f[i][j][k][p] = max(f[i][j][k][p], f[i][j][k - 1][p] + a[r]);
                    if (p)f[i][j][k][p] = max(f[i][j][k][p], f[i][j][k][p - 1] + a[r]);
                }
            }
        }
    }
    cout << f[num[1]][num[2]][num[3]][num[4]] << '\n';
}

P1868 饥饿的奶牛

线性 DP 还可以这样

将 $f_{i}$ 定义为前 $i$ 个格子能吃到多少草。

容易知道 $f_{i} \geq f_{i - 1}$ 恒成立，越到后面吃的草肯定不会变少。

若有加入一个区间 $[i, j]$ ，那么 $f_{j} \geq f_{j - 1} = f_{i - 1} + j - i + 1$

状态转移方程： $f_{j} = max (f_{j}, f_{i - 1} + j - i + 1)$

看起来是二维的，实际上是线性的，这种类似于邻接表建图的方式值得参考。

for Solution in LuoGu: {
	vector<int> g[3000010];
	int f[3000010];
	void solve() {
	    int n;cin >> n;
	    int mx = 0;
	    for (int i = 1;i <= n;i++) {
	        int x, y;cin >> x >> y;g[y].push_back(x - 1);mx = max(mx, y);
	    }
	    for (int i = 1;i <= mx;i++) {
	        f[i] = f[i - 1];
	        for (int j = 0;j < g[i].size();j++) {
	            f[i] = max(f[i], f[g[i][j]] + i - g[i][j]);
	        }
	    }
	    cout << f[mx] << '\n';
	}
}

更容易理解的方式：

vector<int> g[3000010];int f[3000010];
void solve() {
    int n;cin >> n;
    int mx = 0;
    for (int i = 1;i <= n;i++) {
        int x, y;cin >> x >> y;g[y].push_back(x);mx = max(mx, y);
    }
    for (int j = 1;j <= mx;j++) {
        f[j] = f[j - 1];
        for (auto i : g[j]) {
            f[j] = max(f[j], f[i - 1] + j - i + 1);
        }
    }
    cout << f[mx] << '\n';
}

P2679 子串

4 维 DP

$f [i] [j] [p] [0 | 1]$ 代表到 $s_{1}$ 串的第 $i$ 位，匹配了 $s_{2}$ 串的前 $j$ 位，选择了 $p$ 个非空子串，在第 $i$ 个位置选/不选的方案数

当 $a_{i} = b_{j}$ 时

若不选择当前位置，则当前方案数就是前一位选与不选之和 $f [] [] [p] [0] = f [- 1] [] [p] [0] + f [- 1] [] [p] [0]$
若选择当前位置，则当前方案数就是 $f [] [] [p] [1] = f [- 1] [- 1] [p] [1] + f [- 1] [- 1] [p - 1] [0] + f [- 1] [- 1] [p - 1] [1]$

当 $a_{i} \neq b_{j}$ 时

若不选择，仍然是前一位选与不选之和
若选择，但是这个时候不匹配选不了，则方案数为 0

考虑到第一维每次只涉及到 $i, (i - 1)$ ，则可以用滚动数组优化掉第一维避免空间炸掉。

#define int long long
const int mod = 1e9 + 7;
int f[2][210][210][2];
void solve() {
    int n, m, k;cin >> n >> m >> k;
    string s1, s2;cin >> s1 >> s2;s1 = ' ' + s1;s2 = ' ' + s2;
    f[0][0][0][0] = f[1][0][0][0] = 1;
    for (int i = 1, v = 1;i <= n;i++, v ^= 1) {
        for (int j = 1;j <= m;j++) {
            for (int p = 1;p <= k;p++) {
                if (s1[i] == s2[j]) {
                    f[v][j][p][0] = f[v ^ 1][j][p][0] + f[v ^ 1][j][p][1];
                    f[v][j][p][1] = f[v ^ 1][j - 1][p][1] + f[v ^ 1][j - 1][p - 1][0] 
										                  + f[v ^ 1][j - 1][p - 1][1];
                } else {
                    f[v][j][p][0] = f[v ^ 1][j][p][0] + f[v ^ 1][j][p][1];
                    f[v][j][p][1] = 0;
                }
                f[v][j][p][0] %= mod;f[v][j][p][1] %= mod;
            }
        }
    }
    cout << (f[n & 1][m][k][0] + f[n & 1][m][k][1]) % mod << '\n';
}