基础动态规划问题(1)

线性DP

数字三角形问题

定义状态表示f[i][j]代表到达当前位置(i, j)的最大价值, 对于当前位置可以观察可以由哪个位置转移过来f[i - 1][j - 1]或者f[i - 1][j + 1]

#include <bits/stdc++.h>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n;
int w[N][N];
int f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= i; ++j) {
   
            cin >> w[i][j];
        }
    }

    memset(f, -0x3f, sizeof f);

    f[1][1] = w[1][1];
    for (int i = 2; i <= n; ++i) {
   
        for (int j = 1; j <= i; ++j) {
   
            int val1 = -INF, val2 = -INF;
            if (i - 1 >= 1 && j - 1 >= 1) val1 = f[i - 1][j - 1] + w[i][j];
            if (i - 1 >= 1) val2 = f[i - 1][j] + w[i][j];
            f[i][j] = max({
   f[i][j], val1, val2});
        }
    }

    int res = -INF;
    for (int i = 1; i <= n; ++i) res = max(res, f[n][i]);

    cout << res << '\n';
    return 0;
}

最长上升子序列问题

将结果看作一个集合, 最终的目标是集合的代表元素, 定义状态表示f[i], 以w[i]为结尾的最长上升子序列的长度, 考虑状态转移, 当前状态是由倒数第二个数是哪个数字来划分, 朴素做法算法时间复杂度$O(n^2)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i <= n; ++i) f[i] = 1;

    int res = 1;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j < i; ++j) {
   
            if (w[j] < w[i]) f[i] = max(f[i], f[j] + 1);
        }
        res = max(res, f[i]);
    }

    cout << res << '\n';
    return 0;
}

优化后的最长上升子序列算法

数据范围来到了$10^5$, 不能使用朴素的做法, 需要进行优化, 优化后的算法时间复杂度$O(n\log n)$, 下面是优化的过程

将所有的子序列按照长度进行划分, 每个相同长度的子序列只存储结尾值最小的子序列, 我们假设如下的情况

我们假设, 随着子序列长度的增大, 子序列结尾的最小值是变大的

假设f[x1] <= f[x0], 观察x1的前一个数字, 因为子序列是严格单调的, 因此结尾的前一个数t是严格小于f[x1]的, 那么得到f[x0] >= f[x1] > t, 也就是f[x0] > t, 与假设相矛盾(假设是f[x0]是x0长度下的最小值), 因此随着子序列长度的增大, 子序列结尾最小值一定是严格单调递增的

对于当前要插入的数字w来说插入到小于w最大的数后面是最好的, 因为如果插入到非最大数后面, 会造成上述单调性失效, 并且直观来说插入到较小的数后面中间的位置就被浪费了并不是最优的情况

假设小于w最大的数是f[x0], 下一个数是f[x1], 因为f[x1] > w, 又因为当前加入了w, x0 = x0 + 1 = x1, f[x1]也要被更新为w, 并且单调性不会发生改变

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    int len = 0;
    for (int i = 1; i <= n; ++i) {
   
        int l = 0, r = len;
        while (l < r) {
   
            int mid = l + r + 1 >> 1;
            if (f[mid] < w[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        f[l + 1] = w[i];
    }

    cout << len << '\n';
    return 0;
}

最长公共子序列问题

f[i][j]代表考虑第一个字符串前i个字符, 第二个字符串前j个字符的最长公共子序列的集合, 考虑状态转移如果当前
两个字符相等s1[i] == s2[j], f[i][j] = ,max(f[i][j], f[i - 1][j - 1] + 1), 如果当前两个字符不相等, 无法组成公共子序列, 考虑从上一步转移

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
string s1, s2;
int f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    cin >> s1 >> s2;
    s1 = ' ' + s1;
    s2 = ' ' + s2;

    int res = 0;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            f[i][j] = f[i - 1][j - 1];
            if (s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1] + 1;
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            res = max(res, f[i][j]);
        }
    }

    cout << res << '\n';
    return 0;
}

最短编辑距离问题

因为涉及到两个字符串, 自然而然的想到状态表示对于第一个字符串的前i个字符, 并且对于目标字符串的前j个字符, 使得A字符串变为B字符串的方式的集合, 那么当前集合是如何得到的?
需要考虑最后一步的操作是什么, 分为三种情况, 如果最后一步是删除操作, 那么状态转移是f[i - 1][j] + 1, 添加一个字符, 一定是添加s2[j]这个字符, 状态转移是f[i][j - 1] + 1, 最后是修改, 状态转移是f[i - 1][j - 1] + 1

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
string s1, s2;
int f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s1;
    s1 = ' ' + s1;
    cin >> m >> s2;
    s2 = ' ' + s2;

    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++i) f[i][0] = i;
    for (int i = 1; i <= m; ++i) f[0][i] = i;
    f[0][0] = 0;

    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);
            if (s1[i] == s2[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    }

    cout << f[n][m] << '\n';
    return 0;
}

编辑距离问题

编辑距离问题

注意不要重复性的调用memset函数, 这样会导致超时, 非必要情况下不要频繁调用memset函数!!!, 因为循环是从前向后, 因此只需要初始化第一行和第一列

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
string w[N];

int f[N][N];
string s;
int cnt;

int calc_min_cnt(string &s1, string &s2) {
   
    int n1 = s1.size(), n2 = s2.size();
    
    for (int i = 0; i <= n1; ++i) f[i][0] = i;
    for (int i = 0; i <= n2; ++i) f[0][i] = i;

    for (int i = 1; i <= n1; ++i) {
   
        for (int j = 1; j <= n2; ++j) {
   
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (s1[i] == s2[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    }

    return f[n1][n2];
}

int handle() {
   
    int res = 0;
    for (int i = 1; i <= n; ++i) {
   
        if (calc_min_cnt(w[i], s) <= cnt) res++;
    }
    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> w[i], w[i] = ' ' + w[i];

    while (m--) {
   
        cin >> s >> cnt;
        s = ' ' + s;
        cout << handle() << '\n';
    }

    return 0;
}

摘花生问题

参考数字三角形模型, 算法时间复杂度$O(NM)$

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 110;

int n, m;
int w[N][M];

void solution() {
   
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            cin >> w[i][j];
        }
    }

    int f[N][M] = {
   0};
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            f[i][j] = w[i][j];
            if (i - 1 >= 1) f[i][j] = max(f[i][j], f[i - 1][j] + w[i][j]);
            if (j - 1 >= 1) f[i][j] = max(f[i][j], f[i][j - 1] + w[i][j]);
        }
    }

    cout << f[n][m] << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

     int T;
     cin >> T;
     while (T--) {
   
         solution();
     }

    return 0;
}

最低通行费问题

要求最小费用同时在$2N-1$时间内走出, 那么商人只能向右或者向下走, 也就是不能走回头路, 定义状态表示f[i][j]到达当前位置的最小花费

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= n; ++j) {
   
            cin >> w[i][j];
        }
    }

    memset(f, 0x3f, sizeof f);

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= n; ++j) {
   
            if (i == 1 && j == 1) f[i][j] = w[i][j];
            if (i - 1 >= 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
            if (j - 1 >= 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
        }
    }

    cout << f[n][n] << '\n';
    return 0;
}

方格取数

定义状态表示f[k][i1][i2], 表示i1 + j1 = k并且第一遍走到了(i1, k - i1), 第二遍走到了(i2, ki - i2)的最大价值的方案, 转移分为四种情况, 算法时间复杂度$O(n^3)$

#include <bits/stdc++.h>

using namespace std;

const int N = 11;

int n;
int w[N][N];
int f[2 * N][N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    int x, y, val;
    while (cin >> x >> y >> val, x && y && val) w[x][y] = val;

    for (int k = 2; k <= 2 * n; ++k) {
   
        for (int i1 = 1; i1 <= n; ++i1) {
   
            for (int i2 = 1; i2 <= n; ++i2) {
   
                int j1 = k - i1, j2 = k - i2;

                if (j1 < 1 || j1 > n || j2 < 1 || j2 > n) continue;

                int val = w[i1][j1] + (i1 == i2 ? 0 : w[i2][j2]);
                f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2] + val);

                if (i1 > 1) f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2] + val);
                if (i2 > 1) f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + val);
                if (i1 > 1 && i2 > 1) f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + val);
            }
        }
    }

    int res = f[2 * n][n][n];
    cout << res << '\n';
    return 0;
}

传纸条问题

问题抽象后和方格取数问题类似, 定义状态表示f[k][i1][i2], 算法时间复杂度$O(n^3)$

#include <bits/stdc++.h>

using namespace std;

const int N = 50 + 1;

int n, m;
int w[N][N], f[2 * N][N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            cin >> w[i][j];
        }
    }

    for (int k = 2; k <= n + m; ++k) {
   
        for (int i1 = 1; i1 <= n; ++i1) {
   
            for (int i2 = 1; i2 <= n; ++i2) {
   
                int j1 = k - i1, j2 = k - i2;
                if (j1 < 1 || j1 > m || j2 < 1 || j2 > m) continue;
                int val = w[i1][j1] + (i1 == i2 ? 0 : w[i2][j2]);
                f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2] + val);
                if (i1 > 1) f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2] + val);
                if (i2 > 1) f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + val);
                if (i1 > 1 && i2 > 1) f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + val);
            }
        }
    }

    int res = f[n + m][n][n];
    cout << res << '\n';

    return 0;
}

怪盗基德的滑翔翼

初始的时候可以在任意一栋建筑开始, 只能向一个方向移动, 那么求两次最长上升子序列取最大值就是结果, 使用二分优化后的算法时间复杂度$O(n\log n)$

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, w[N];

void solution() {
   
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    int f[N] = {
   0}, g[N] = {
   0};

    int len1 = 0;
    for (int i = 1; i <= n; ++i) {
   
        int l = 0, r = len1;
        while (l < r) {
   
            int mid = l + r + 1 >> 1;
            if (f[mid] < w[i]) l = mid;
            else r = mid - 1;
        }
        len1 = max(len1, l + 1);
        f[l + 1] = w[i];
    }

    int len2 = 0;
    for (int i = n; i >= 1; --i) {
   
        int l = 0, r = len2;
        while (l < r) {
   
            int mid = l + r + 1 >> 1;
            if (g[mid] < w[i]) l = mid;
            else r = mid - 1;
        }
        len2 = max(len2, l + 1);
        g[l + 1] = w[i];
    }

    int res = max(len1, len2);
    cout << res << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;

    while (T--) {
   
        solution();
    }

    return 0;
}

登山问题

上山之后不再下山了, 说明顶点就是分界点, 定义状态表示f[i]以i为结尾的最长上升子序列, g[i]以i为结尾的反向的最长上升子序列, 那么结果就是res = max(f[i] + g[i] - 1), 因为需要记录每个点为结尾的最长上升子序列, 不能进行二分优化, 算法时间复杂度$O(n^2)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

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

    int res = 1;
    for (int i = 1; i <= n; ++i) res = max(res, f[i] + g[i] - 1);

    cout << res << '\n';
    return 0;
}

合唱队形问题

也就是求最长先上升再下降的序列, 结果就是res = len - max(f[i] + g[i] - 1), 求解的过程和上面的登山类似, 算法时间复杂度$O(n^2)$

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    for (int i = 1; i <= n; ++i) {
   
        f[i] = 1;
        for (int j = 1; j < i; ++j) {
   
            if (w[j] < w[i]) f[i] = max(f[i], f[j] + 1);
        }
    }

    for (int i = n; i >= 1; --i) {
   
        g[i] = 1;
        for (int j = n; j > i; --j) {
   
            if (w[j] < w[i]) g[i] = max(g[i], g[j] + 1);
        }
    }

    int res = 1;
    for (int i = 1; i <= n; ++i) res = max(res, f[i] + g[i] - 1);

    cout << n - res << '\n';
    return 0;
}

最大上升子序列和问题

将结果集合按照子序列的最后一个数进行划分, f[i]代表以w[i]为结尾的最大上升子序列和的集合, 属性是最大值, 算法时间复杂度$O(n^2)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    for (int i = 1; i <= n; ++i) {
   
        f[i] = w[i];
        for (int j = 1; j < i; ++j) {
   
            if (w[j] < w[i]) f[i] = max(f[i], f[j] + w[i]);
        }
    }

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

    cout << res << '\n';
    return 0;
}

拦截导弹问题

第一问很简单, 直接求非严格的最长下降子序列的长度
第二问采用贪心的思路
对于当前导弹的高度, 有两种选择, 创建一个新的防御系统或者接在已有的防御系统后面

• 如果不能接在已有的导弹系统后面, 那么新建一个系统
• 否则, 因为要求的拦截系统数量尽可能地少, 尝试接在已有的防御系统后面, 我们将当前导弹w[i]接到, $\ge w[i]$最小的结尾的位置

证明:
假设贪心法得到的最少系统的数量是$A$, 最优解得到的最少系统数量是$B$, 因为$B$是最优解, 因此$B\le A$

因为$\ge w[i]$最小的数是$x$, 因此$y\ge x$

尝试将两个序列进行交换, 发现不产生冲突并且导弹防御系统的数量没有增多也没有减少
得到结论, 只要是贪心解法和最优解不同, 一定可以通过有限次的交换使得两个结果变得相同
因为每一次调整都没有增加子序列的个数, 因此$A\le B$, 又因为$A\ge B$, 因此$A=B$, 也就是说贪心法得到的数量等于最优解的数量

定义g[i]表示长度为i的最长下降子序列的结尾(也就是 $\ge w[i]$最小的数), 可以证明随着i增大, g[i]也会增大
在二分优化的$LIS$问题中已经证明, 这里情况类似

狄尔沃斯定理: 一个序列的最长上升子序列的长度 = 使用最少的下降子序列覆盖该序列的数量

整体的算法时间复杂度$O(n\log n)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> w[++n]);

    n--;
    int len = 0;
    for (int i = 1; i <= n; ++i) {
   
        int l = 0, r = len;
        // f[i]表示长度为i的非递增子序列的结尾最小值, 二分出>=w[i]的最小值
        while (l < r) {
   
            int mid = l + r + 1 >> 1;
            if (f[mid] >= w[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        f[l + 1] = w[i];
    }
    cout << len << '\n';

    int idx = 0;
    for (int i = 1; i <= n; ++i) {
   
        int l = 0, r = idx;
        // g[i]代表拦截系统的编号是i, g[i]是当前拦截系统的最后一个导弹高度
        while (l < r) {
   
            int mid = l + r >> 1;
            if (g[mid] >= w[i]) r = mid;
            else l = mid + 1;
        }
        if (l == idx) g[idx++] = w[i];
        else g[l] = w[i];
    }

    cout << idx << '\n';
    return 0;
}

导弹防御系统问题

观察导弹数量不超过$50$, 可以使用暴力的做法解决, 高度要么严格上升要么严格下降, 使用dfs解决, 算法时间复杂度$O(n^2)$, 需要对递归搜索树进行剪枝

#include <bits/stdc++.h>

using namespace std;

const int N = 60;

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

void dfs(int u, int up_cnt, int down_cnt) {
   
    if (up_cnt + down_cnt >= res) return;

    if (u > n) {
   
        res = min(res, up_cnt + down_cnt);
        return;
    }

    int k = 0;
    while (k < down_cnt && down[k] <= w[u]) k++;
    if (k == down_cnt) {
   
        down[down_cnt] = w[u];
        dfs(u + 1, up_cnt, down_cnt + 1);
    }
    else {
   
        int val = down[k];
        down[k] = w[u];
        dfs(u + 1, up_cnt, down_cnt);
        down[k] = val;
    }

    k = 0;
    while (k < up_cnt && up[k] >= w[u]) k++;
    if (k == up_cnt) {
   
        up[up_cnt] = w[u];
        dfs(u + 1, up_cnt + 1, down_cnt);
    }
    else {
   
        int val = up[k];
        up[k] = w[u];
        dfs(u + 1, up_cnt, down_cnt);
        up[k] = val;
    }
}

void solution() {
   
    for (int i = 1; i <= n; ++i) cin >> w[i];
    res = n;
    dfs(1, 0, 0);
    cout << res << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    while (cin >> n, n) solution();

    return 0;
}

另一种写法

#include <bits/stdc++.h>

using namespace std;

const int N = 60;

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

void dfs(int u, int up_cnt, int down_cnt) {
   
    if (up_cnt + down_cnt >= res) return;

    if (u > n) {
   
        res = min(res, up_cnt + down_cnt);
        return;
    }

    int k = 0;
    while (k < down_cnt && down[k] <= w[u]) k++;
    if (k == down_cnt) {
   
        down[down_cnt++] = w[u];
        dfs(u + 1, up_cnt, down_cnt);
        down_cnt--;
    }
    else {
   
        int val = down[k];
        down[k] = w[u];
        dfs(u + 1, up_cnt, down_cnt);
        down[k] = val;
    }

    k = 0;
    while (k < up_cnt && up[k] >= w[u]) k++;
    if (k == up_cnt) {
   
        up[up_cnt++] = w[u];
        dfs(u + 1, up_cnt, down_cnt);
        up_cnt--;
    }
    else {
   
        int val = up[k];
        up[k] = w[u];
        dfs(u + 1, up_cnt, down_cnt);
        up[k] = val;
    }
}

void solution() {
   
    for (int i = 1; i <= n; ++i) cin >> w[i];
    res = n;
    dfs(1, 0, 0);
    cout << res << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    while (cin >> n, n) solution();

    return 0;
}

最长公共上升子序列问题

定义状态表示f[i][j]对于第一个字符串的前i个字符和第二个字符串的前j个字符并且以B[j]结尾的公共上升子序列的集合, 属性是长度最大值, 集合的划分是子序列中是否包含A[i], 如果不包含A[i], 上一个状态就是f[i - 1][j], 如果包含A[i], 前提条件是A[i] == B[j]

状态转移观察的是当前状态怎么由上一个状态转移过来, 对于当前集合, s1子序列的结尾是s1[i], s2子序列的结尾是s2[j], 那么计算上一个状态就是f[i - 1][k] + 1

朴素做法的时间复杂度$O(n^3)$

#include <bits/stdc++.h>

using namespace std;

const int N = 3010;

int n, s1[N], s2[N];
int f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> s1[i];
    for (int i = 1; i <= n; ++i) cin >> s2[i];

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= n; ++j) {
   
            f[i][j] = f[i - 1][j];
            if (s1[i] == s2[j]) {
   
                int val = 1;
                for (int k = 1; k < j; ++k) {
   
                    if (s2[k] < s2[j]) val = max(val, f[i - 1][k] + 1);
                }
                f[i][j] = max(f[i][j], val);
            }
        }
    }

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

    cout << res << '\n';
    return 0;
}

优化后的代码使用val记录最大值前缀节省一维时间, 算法时间复杂度$O(n^2)$

因为当前求的是f[i][j], val记录的信息是i - 1层的情况, 并且也是$[1,j-1]$的最大值

#include <bits/stdc++.h>

using namespace std;

const int N = 3010;

int n, s1[N], s2[N];
int f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> s1[i];
    for (int i = 1; i <= n; ++i) cin >> s2[i];

    for (int i = 1; i <= n; ++i) {
   
        int val = 1;
        for (int j = 1; j <= n; ++j) {
   
            f[i][j] = f[i - 1][j];
            if (s1[i] == s2[j]) f[i][j] = max(f[i][j], val);
            if (s2[j] < s1[i]) val = max(val, f[i - 1][j] + 1);
        }
    }

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

    cout << res << '\n';
    return 0;
}

背包问题

01背包问题

定义状态表示f[i][j], 表示考虑前i个物品, 总体积不超过j, 的选择方案中价值最大的方案的价值, 对于f[i][j]方案可以由当前物品的选择情况进行划分, 如果不选择当前物品f[i - 1][j], 如果选择当前物品价值就是f[i - 1][j - v[i]] + w[i], 因为当前状态是由f[i - 1]层数给出, 因此数组可以省下一个维度, 使用f[j]代替状态表示, 但是第二层体积需要进行倒序枚举, 因为对于当前状态f[i][j]需要的状态是f[i - 1][x] x < j

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 1010;

int n, m;
int w[N], v[N];
int f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; ++i) {
   
        for (int j = m; j >= v[i]; --j) {
   
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << '\n';
    return 0;
}

完全背包问题

状态表示不需要发生改变, 因为物品数量是无限的, 状态转移方式需要改变, 对于当前物品可选择的次数上限是$\frac{m}{v[i]}$

状态计算
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - 2 * v[i]] + 2 * w[i] , ... , f[i - 1][j - k * v[i]] + k * w[i])
再观察f[i][j - v[i]]的计算过程
f[i][j - v[i]] = max(f[i - 1][j - v[i]], f[i - 1][j - 2 * v[i]] + w[i], f[i - 1][j - k * v[i]] + (k - 1) * w[i])

状态转移方程转化为f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]), 对比01背包问题的状态转移方程, 因为当前层状态只与上一层状态有关, 因此也可以优化掉一维, 但是因为当前状态f[i][j], 需要的上一层状态是f[i - 1][j]并且需要当前i层数的f[i][j - v[i]]状态, 只能正序枚举体积j, 状态转移方程优化为f[j] = max(f[j], f[j - v[i]] + w[i])

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 1010;

int n, m;
int w[N], v[N];
int f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; ++i) {
   
        for (int j = v[i]; j <= m; ++j) {
   
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << '\n';
    return 0;
}

多重背包问题及其优化

多重背包问题朴素算法$O(n\times m\times c)$

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 110;

int n, m;
int v[N], w[N], c[N];
int f[N][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> c[i];

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 0; j <= m; ++j) {
   
            f[i][j] = f[i - 1][j];
            for (int k = 0; k <= min(c[i], j / v[i]); ++k) {
   
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }

    cout << f[n][m] << '\n';
    return 0;
}

多重背包问题二进制优化$O(n\times m\times logC)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 2010;

int n, m;
int v[N], w[N], c[N];
int new_v[N * 12], new_w[N * 12];
int f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> c[i];

    int cnt = 1;
    for (int i = 1; i <= n; ++i) {
   
        int val = 1;

        while (val <= c[i]) {
   
            new_v[cnt] = val * v[i];
            new_w[cnt++] = val * w[i];
            c[i] -= val;
            val <<= 1;
        }

        if (c[i]) {
   
            new_v[cnt] = c[i] * v[i];
            new_w[cnt++] = c[i] * w[i];
        }
    }

    for (int i = 1; i <= cnt; ++i) {
   
        for (int j = m; j >= new_v[i]; --j) {
   
            f[j] = max(f[j], f[j - new_v[i]] + new_w[i]);
        }
    }

    cout << f[m] << '\n';
    return 0;
}

多重背包问题单调队列优化$O(n\times m)$
对比完全背包问题, 当前物品选择的数量上限不是$\frac{m}{v[i]}$, 而是$\min (\frac{m}{v[i]},s_i)$
观察当前的状态转移方程

f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - 2 * v[i]] + 2 * w[i], ... , f[i - 1][j - s * v[i]] + s * w[i])

f[i][j - v] = max(f[i - 1][j - v[i]], f[i - 1][j - 2 * v[i]] + w[i], ... , f[i - 1][j - s * v[i]] + (s - 1) * w[i], f[i - 1][j - (s + 1) * v[i] + s * w[i])
继续向下写, 发现最后是f[i][r], 其中r = m % v[i]

将所有的情况划分到数轴上, 从左向右开始滑, 当窗口大小达到s的时候记录单调队列队头的最大值, 每个窗口相较于上一个窗口实际的值的偏移量是w

观察状态转移方程, f[i]状态只与f[i - 1]状态有关, 可以使用01背包问题的优化方式进行优化

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int v[N], w[N], s[N];
int f[M], tmp[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];

    int q[M];
    for (int i = 1; i <= n; ++i) {
   
        memcpy(tmp, f, sizeof f);
        for (int r = 0; r < v[i]; ++r) {
   
            int h = 0, t = -1;
            for (int j = r; j <= m; j += v[i]) {
   
                while (h <= t && j - q[h] > s[i] * v[i]) h++;
                while (h <= t && tmp[j] >= tmp[q[t]] + (j - q[t]) / v[i] * w[i]) t--;
                q[++t] = j;
                f[j] = tmp[q[h]] + (j - q[h]) / v[i] * w[i];
            }
        }
    }

    cout << f[m] << '\n';
    return 0;
}

分组背包问题

注意分组背包问题第二层循环是物品的体积而不是组内物品
因为每个组内的物品只能选择一个, 对于当前体积j, 遍历组内所有物品看选择哪个, 也就是组内的01背包问题
而不是对于当前组内物品选择一个最合适的体积, 这样会导致一个体积j内有多个当前组内的物品, 与题目相违背, 因此第二层循环需要先确定体积再确定组内物品
朴素版写法

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 110;

int n, m;
vector<int> v[N], w[N];
int f[N][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
   
        int cnt;
        cin >> cnt;
        for (int j = 0; j < cnt; ++j) {
   
            int val1, val2;
            cin >> val1 >> val2;
            v[i].push_back(val1), w[i].push_back(val2);
        }
    }

    for (int i = 1; i <= n; ++i) {
   
        int cnt = v[i].size();
        for (int j = 0; j <= m; ++j) {
   
            f[i][j] = f[i - 1][j];
            for (int k = 0; k < cnt; ++k) {
   
                if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }

    cout << f[n][m] << '\n';
    return 0;
}

发现当前组状态f[i]只与上一层状态f[i - 1]有关, 可以使用01背包问题的优化方式进行优化, 优化版写法

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 110;

int n, m;
vector<int> v[N], w[N];
int f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
   
        int cnt;
        cin >> cnt;
        for (int j = 0; j < cnt; ++j) {
   
            int val1, val2;
            cin >> val1 >> val2;
            v[i].push_back(val1), w[i].push_back(val2);
        }
    }

    for (int i = 1; i <= n; ++i) {
   
        int cnt = v[i].size();
        for (int j = m; j >= 0; --j) {
   
            for (int k = 0; k < cnt; ++k) {
   
                if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
        }
    }

    cout << f[m] << '\n';
    return 0;
}

树上背包问题

选择当前节点必须选择当前节点的父节点, 也就是当前节点依赖于父节点, 对于树上问题f[u][j], 以u为根节点给当前子树分配j的体积的所有选择方案中最大价值的方案

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 110;

int n, m;
int head[N], ed[M], ne[M], idx;
int v[N], w[N];
int f[N][M];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void dfs(int u) {
   
    for (int i = v[u]; i <= m; ++i) f[u][i] = w[u];

    for (int i = head[u]; ~i; i = ne[i]) {
   
        int ver = ed[i];
        dfs(ver);
        for (int j = m; j >= v[u]; --j) {
   
            for (int k = 0; k <= j - v[u]; ++k) {
   
                f[u][j] = max(f[u][j], f[u][j - k] + f[ver][k]);
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(head, -1, sizeof head);

    int root = 0;
    cin >> n >> m;
    
    for (int i = 1; i <= n; ++i) {
   
        int fa;
        cin >> v[i] >> w[i] >> fa;
        if (fa == -1) root = i;
        else add(fa, i);
    }

    dfs(root);

    cout << f[root][m] << '\n';
    return 0;
}

在合并子节点ver时，f[u][j - k] 表示在考虑当前子节点之前，u 在容量 j - k 下的最大价值。
如果j从小到大循环，那么 f[u][j - k] 可能已经包含了当前子节点ver的贡献（因为 j - k < j，可能已经在本轮被更新过），这样就会发生重复选取同一个子节点多次的错误, 因此体积只能倒序循环

采药问题

01背包问题, 优化掉一维, 算法时间复杂度$O(nm)$

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1010;

int n, m;
int v[N], w[N];
int f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> m >> n;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; ++i) {
   
        for (int j = m; j >= v[i]; --j) {
   
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << '\n';

    return 0;
}

装箱问题

剩余空间最小等于装箱体积最大, 依旧是01背包问题, 算法时间复杂度$O(nm)$

#include <bits/stdc++.h>

using namespace std;

const int N = 31, M = 20010;

int n, m;
int v[N], w[N];
int f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> m >> n;
    for (int i = 1; i <= n; ++i) {
   
        cin >> v[i];
        w[i] = v[i];
    }

    for (int i = 1; i <= n; ++i) {
   
        for (int j = m; j >= v[i]; --j) {
   
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    int res = m - f[m];
    cout << res << '\n';

    return 0;
}

数字组合问题

因为每个数字只能选择一次, 相当于01背包问题求方案数, 定义状态表示f[i][j]表示考虑前i 个数字, 并且总和恰好为j的所有方案的数量, 状态转移是当前数字是否考虑, 如果不考虑需要累加该状态f[i - 1][j], 如果考虑当前数字, 累加该状态f[i - 1][j - v[i]]

依旧是与上一层状态有关, 还是能优化掉一维, 算法时间复杂度$O(nm)$

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 10010;

int n, m;
int v[N];
int f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i];

    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = m; j >= v[i]; --j) {
   
            f[j] += f[j - v[i]];
        }
    }

    cout << f[m] << '\n';

    return 0;
}

买书问题

完全背包问题求方案数量, 根据状态转移进行优化, f[i][j] = f[i - 1][j] + f[i][j - v[i]], 优化掉一维, 算法时间复杂度$O(4n)$

#include <bits/stdc++.h>

using namespace std;

const int v[5] = {
   0, 10, 20, 50, 100};
const int N = 1010;

int n;
int f[N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    f[0] = 1;
    for (int i = 1; i <= 4; ++i) {
   
        for (int j = v[i]; j <= n; ++j) {
   
            f[j] += f[j - v[i]];
        }
    }

    cout << f[n] << '\n';

    return 0;
}

货币系统问题

本质还是完全背包问题求方案数, 注意方案书很大, 需要取long long

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 20, M = 3010;

int n, m;
int v[N];
LL f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i];

    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = v[i]; j <= m; ++j) {
   
            f[j] += f[j - v[i]];
        }
    }

    cout << f[m] << '\n';
    return 0;
}

货币系统(CSP)

目标是求最少是用的货币数量, 使得得到的最大独立集等于给定的线性空间

假设最终结果的最大独立集合是b[i], 原始的线性空间是a[i]

性质如下

1. a[i]集合能被b[i]集合表示, 也就是$a_i=b_0\times t_0+b_1\times t_1+...+b_n\times t_n$
2. b集合一定是从a集合中选择的
3. $b_1,b_2,b_3,...,b_n$不能被其他的$b_i$表示出来

性质2的证明
假设最优解中存在一个数字$b_m$, 因为集合b是集合a的最大独立集, 因此$b_m=a_0\times t_0+b_1\times t_1+...+b_n\times t_n$, 又因为b集合是a集合的最大独立集, 因此$a_i=b_0\times t_0+b_1\times t_1+...+b_n\times t_n$
也就是说$b_m=b_0\times c_0+b_1\times c_1+...+b_n\times c_n$
也就是说$b_m$能被b集合本身表示出来, 那么说明b集合不是最优解, 也就说明不存在一个数字b_m不属于a集合
也就说明b集合的所有数字来源于a集合

具体的做法
因为给定的$a_i$是正整数, 将给定的a集合进行排序, 对于当前的$a_i$需要判断是否能被$a_0,a_1,a_2,...,a_{i-1}$表示出来, 可以被表示出来一定不选择, 不可被表示必须选择, 可以使用完全背包问题进行优化, 是否能恰好装满$a_i$这个容量的背包

算法时间复杂度$O(n^{2}m)$, $m\le 25000$

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 25010;

int n, w[N];

void solution() {
   
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    sort(w + 1, w + n + 1);

    int f[M];

    int res = 0;
    for (int i = 1; i <= n; ++i) {
   
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int j = 1; j < i; ++j) {
   
            for (int k = w[j]; k <= w[i]; ++k) {
   
                f[k] += f[k - w[j]];
            }
        }
        if (f[w[i]] == 0) res++;
    }

    cout << res << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
   
        solution();
    }

    return 0;
}

庆功会问题

多重背包问题, 可以使用单调队列进行优化, 算法时间复杂度$O(nm)$

#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 6010;

int n, m;
int v[N], w[N], s[N];
int f[M], tmp[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];

    int q[M];
    for (int i = 1; i <= n; ++i) {
   
        memcpy(tmp, f, sizeof f);
        for (int r = 0; r < v[i]; ++r) {
   
            int h = 0, t = -1;
            for (int j = r; j <= m; j += v[i]) {
   
                while (h <= t && j - q[h] > s[i] * v[i]) h++;
                while (h <= t && tmp[j] >= tmp[q[t]] + (j - q[t]) / v[i] * w[i]) t--;
                q[++t] = j;
                f[j] = tmp[q[h]] + (j - q[h]) / v[i] * w[i];
            }
        }
    }

    cout << f[m] << '\n';
    return 0;
}

混合背包问题

可以将所有问题转换为01背包问题, 也就是将完全背包和多重背包问题使用二进制拆分, 然后统一使用01背包优化方式解决
或者将所有背包问题转化为多重背包问题
多重背包写法, 算法时间复杂度$O(nm)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 1010;

int n, m;
int v[N], w[N], s[N];
int f[M], tmp[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
   
        int cnt;
        cin >> v[i] >> w[i] >> cnt;
        if (cnt == -1) s[i] = 1;
        else if (cnt == 0) s[i] = m / v[i];
        else s[i] = cnt;
    }

    int q[M];
    for (int i = 1; i <= n; ++i) {
   
        memcpy(tmp, f, sizeof f);
        for (int r = 0; r < v[i]; ++r) {
   
            int h = 0, t = -1;
            for (int j = r; j <= m; j += v[i]) {
   
                while (h <= t && j - q[h] > s[i] * v[i]) h++;
                while (h <= t && tmp[j] >= tmp[q[t]] + (j - q[t]) / v[i] * w[i]) t--;
                q[++t] = j;
                f[j] = tmp[q[h]] + (j - q[h]) / v[i] * w[i];
            }
        }
    }

    cout << f[m] << '\n';
    return 0;
}

二维费用的背包问题

定义状态表示f[i][j][k]表示考虑前i个物品, 并且总体积不超过j并且总重量不超过k的所有方案, 属性是最大值, 本质就是01背包问题新增一维, 算法时间复杂度$O(n\times v\times m)$
朴素做法(128ms)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, V = 110, M = 110;

int n, v, m;
int v1[N], v2[N], w[N];
int f[N][V][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> v >> m;
    for (int i = 1; i <= n; ++i) cin >> v1[i] >> v2[i] >> w[i];

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 0; j <= v; ++j) {
   
            for (int k = 0; k <= m; ++k) {
   
                f[i][j][k] = f[i - 1][j][k];
                if (j >= v1[i] && k >= v2[i]) f[i][j][k] = max(f[i][j][k], f[i - 1][j - v1[i]][k - v2[i]] + w[i]);
            }
        }
    }

    cout << f[n][v][m] << '\n';

    return 0;
}

空间优化做法(28ms)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, V = 110, M = 110;

int n, v, m;
int v1[N], v2[N], w[N];
int f[V][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> v >> m;
    for (int i = 1; i <= n; ++i) cin >> v1[i] >> v2[i] >> w[i];

    for (int i = 1; i <= n; ++i) {
   
        for (int j = v; j >= v1[i]; --j) {
   
            for (int k = m; k >= v2[i]; --k) {
   
                f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + w[i]);
            }
        }
    }

    cout << f[v][m] << '\n';

    return 0;
}

潜水员问题

定义状态表示f[i][j][k]表示考虑前i个气缸, 并且凑出的氧气含量至少是j并且凑出的氮气含量至少是k的所有方案, 属性是重量的最小值, 依旧是将集合进行划分, 对于当前气缸i选择或者不选择, 算法时间复杂度$O(n\times m\times k)$
朴素写法

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 100;

int t, m;
int n;
int v1[N], v2[N], w[N];
int f[N][M][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> t >> m;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> v1[i] >> v2[i] >> w[i];

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i <= n; ++i) f[i][0][0] = 0;

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 0; j <= t; ++j) {
   
            for (int k = 0; k <= m; ++k) {
   
                f[i][j][k] = f[i - 1][j][k];
                int new_j = max(0, j - v1[i]);
                int new_k = max(0, k - v2[i]);
                f[i][j][k] = min(f[i][j][k], f[i - 1][new_j][new_k] + w[i]);
            }
        }
    }


    cout << f[n][t][m] << '\n';
    return 0;
}

因为当前层状态只与上一层状态有关, 可以优化掉一维
优化后写法

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 100;

int t, m;
int n;
int v1[N], v2[N], w[N];
int f[M][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> t >> m;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> v1[i] >> v2[i] >> w[i];

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
   
        for (int j = t; j >= 0; --j) {
   
            for (int k = m; k >= 0; --k) {
   
                int new_j = max(0, j - v1[i]);
                int new_k = max(0, k - v2[i]);
                f[j][k] = min(f[j][k], f[new_j][new_k] + w[i]);
            }
        }
    }

    cout << f[t][m] << '\n';
    return 0;
}

机器分配问题

背包问题求具体方案, 算法时间复杂度$O(n{m}^2)$

#include <bits/stdc++.h>

using namespace std;

const int N = 11, M = 20;

int n, m;
int w[N][M];
int f[N][M], p[N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            cin >> w[i][j];
        }
    }

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 0; j <= m; ++j) {
   
            f[i][j] = f[i - 1][j];
            for (int k = 1; k <= j; ++k) {
   
                int val = f[i - 1][j - k] + w[i][k];
                f[i][j] = max(f[i][j], val);
            }
        }
    }

    cout << f[n][m] << '\n';

    int j = m;
    for (int i = n; i >= 1; --i) {
   
        for (int k = 0; k <= m; ++k) {
   
            if (f[i][j] == f[i - 1][j - k] + w[i][k]) {
   
                p[i] = k;
                j -= k;
                break;
            }
        }
    }

    for (int i = 1; i <= n; ++i) cout << i << ' ' << p[i] << '\n';
    return 0;
}

开心的金明

背包问题的变形, 还是决策当前物品选择或者不选择, 算法时间复杂度$O(nm)$

#include <bits/stdc++.h>

using namespace std;

const int N = 30, M = 30010;

int n, m;
int w[N], fac[N];
int f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> m >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i] >> fac[i];

    for (int i = 1; i <= n; ++i) {
   
        for (int j = m; j >= w[i]; --j) {
   
            f[j] = max(f[j], f[j - w[i]] + fac[i] * w[i]);
        }
    }

    cout << f[m] << '\n';

    return 0;
}

背包问题求方案数

求最优选法的方案数量, 并不是所有的方案数

所有的$dp$问题都可以转换为图论问题, 对于线性$dp$也就是拓扑图, 算法时间复杂度$O(nm)$
朴素写法($51ms$)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 1010, MOD = 1e9 + 7;

int n, m;
int v[N], w[N];
int f[N][M], g[N][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];

    for (int i = 0; i <= n; ++i) g[i][0] = 1;
    for (int j = 0; j <= m; ++j) g[0][j] = 1;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 0; j <= m; ++j) {
   
            f[i][j] = f[i - 1][j];
            g[i][j] = g[i - 1][j];
            if (j >= v[i]) {
   
                int val = f[i - 1][j - v[i]] + w[i];
                if (val > f[i][j]) {
   
                    g[i][j] = g[i - 1][j - v[i]];
                    f[i][j] = val;
                }
                else if (val == f[i][j]) g[i][j] = (g[i][j] + g[i - 1][j - v[i]]) % MOD;
            }
        }
    }

    cout << g[n][m] << '\n';

    return 0;
}

空间优化写法($35ms$)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 1010, MOD = 1e9 + 7;

int n, m;
int v[N], w[N];
int f[M], g[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];

    g[0] = 1;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = m; j >= v[i]; --j) {
   
            int max_v = max(f[j], f[j - v[i]] + w[i]);
            int cnt = 0;
            if (max_v == f[j]) cnt = (cnt + g[j]) % MOD;
            if (max_v == f[j - v[i]] + w[i]) cnt = (cnt + g[j - v[i]]) % MOD;
            f[j] = max_v;
            g[j] = cnt;
        }
    }

    int res = 0;
    for (int j = 0; j <= m; ++j) {
   
        if (f[j] == f[m]) res = (res + g[j]) % MOD;
    }

    cout << res << '\n';
    return 0;
}

背包问题求具体方案

求字典序最小的方案, 因为求字典序最小, 因此计算的时候需要从后向前枚举, 在倒着推的过程中, 才能得到字典序最小的方案

正常的推断求所有方案, 因为最终的状态是f[n][m], 当前状态是由上一个状态f[i - 1][xxx]得到, 因此并非的字典序最小的方案(即便是排序后)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 1010;

int n, m;
int v[N], w[N];
int f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; ++i) {
   
        for (int j = m; j >= v[i]; --j) {
   
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    int j = m;
    for (int i = n; i >= 1; --i) {
   
        if (f[j] == f[j - v[i]] + w[i]) {
   
            cout << i << ' ';
            j -= v[i];
        }
    }
    cout << '\n';

    return 0;
}

正确的做法是先将所有的物品倒序考虑, 重新定义状态表示, 最终的状态是f[1][m], 因为倒着求, 所得到的字典序一定是最小的, 算法时间复杂度$O(nm)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 1010;

int n, m;
int v[N], w[N];
int f[N][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];

    for (int i = n; i >= 1; --i) {
   
        for (int j = 0; j <= m; ++j) {
   
            f[i][j] = f[i + 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    }

    int j = m;
    for (int i = 1; i <= n; ++i) {
   
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
   
            cout << i << ' ';
            j -= v[i];
        }
    }
    cout << '\n';

    return 0;
}

能量石

假设第一个序列得到的能量更多, 那么有不等式
$e_1-l_1\times T+e_2-l_2\times T-l_2\times s_1>e_2-l_1\times T-l_1\times s_2$
整理得到
$$\frac{l_1}{s_1}>\frac{l_2}{s_2}$$
按照该比例, 将所有能量石从小到大排序, 然后从前向后选择, 得到的就是最大能量, 算法时间复杂度$O(nm)$, 时间瓶颈在$dp$

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = N * N;

int n;
struct Stone {
   
    int s, e, l;
    bool operator< (const Stone &u) {
   
        int l2 = u.l, s2 = u.s;
        return l * s2 > l2 * s;
    }
} stones[N];

int solution() {
   
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> stones[i].s >> stones[i].e >> stones[i].l;

    sort(stones + 1, stones + n + 1);

    int f[N][M] = {
   0};
    int res = 0;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 0; j <= 100 * n; ++j) {
   
            f[i][j] = f[i - 1][j];
            if (j >= stones[i].s) {
   
                int val = f[i - 1][j - stones[i].s] + max(0, stones[i].e - stones[i].l * (j - stones[i].s));
                f[i][j] = max(f[i][j], val);
                res = max(res, f[i][j]);
            }
        }
    }

    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    for (int i = 1; i <= T; ++i) {
   
        int res = solution();
        printf("Case #%d: %d\n", i, res);
    }

    return 0;
}

金明的预算方案(NOI)

因为附件的数量不会超过$2$个, 因此可以使用二进制进行枚举附件选择的情况, 算法时间复杂度$O(4nm)$

#include <bits/stdc++.h>

using namespace std;

const int N = 70, M = 32010;

int n, m;
int w[N], fac[N];
vector<int> fa;
vector<int> son[N];
int f[N][M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> m >> n;

    fa.push_back(0);
    for (int i = 1; i <= n; ++i) {
   
        int p;
        cin >> w[i] >> fac[i] >> p;
        if (p == 0) fa.push_back(i);
        else son[p].push_back(i);
    }

    for (int i = 1; i < fa.size(); ++i) {
   
        int u = fa[i];
        for (int j = 0; j <= m; ++j) {
   
            f[i][j] = f[i - 1][j];
            int cnt = son[u].size();
            for (int k = 0; k < 1 << cnt; ++k) {
   
                int v = w[u], max_val = w[u] * fac[u];
                for (int l = 0; l < cnt; ++l) {
   
                    if (k >> l & 1) {
   
                        v += w[son[u][l]];
                        max_val += w[son[u][l]] * fac[son[u][l]];
                    }
                }
                if (j >= v) f[i][j] = max(f[i][j], f[i - 1][j - v] + max_val);
            }
        }
    }

    cout << f[fa.size() - 1][m] << '\n';
    return 0;
}

也可以按有依赖的背包问题解决, 选择当前节点必须选择当前节点的父节点, 算法时间复杂度$O(nm)$

#include <bits/stdc++.h>

using namespace std;

const int N = 70, M = 32010;

int n, m;
int w[N], fac[N];
int head[N], ed[N], ne[N], idx;
int f[N][M];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void dfs(int u) {
   
    for (int j = w[u]; j <= m; ++j) f[u][j] = w[u] * fac[u];
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        dfs(v);
        for (int j = m; j >= w[u]; --j) {
   
            for (int k = 0; k <= j - w[u]; ++k) {
   
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> m >> n;

    int root = N - 1;
    for (int i = 1; i <= n; ++i) {
   
        int fa;
        cin >> w[i] >> fac[i] >> fa;
        if (fa == 0) add(root, i);
        else add(fa, i);
    }

    dfs(root);

    cout << f[root][m] << '\n';
    return 0;
}

状态机DP

大盗阿福

定义状态表示f[i][0]表示考虑前i家客户, 并且不选择当前客户的最大金额, 反之f[i][1]是选择当前客户的最大金额, 状态转移由当前客户选择情况进行划分, 算法时间复杂度$O(n)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, w[N];
int f[N][2];

void solution() {
   
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    memset(f, 0, sizeof f);
    for (int i = 1; i <= n; ++i) {
   
        f[i][0] = max(f[i - 1][0], f[i - 1][1]);
        f[i][1] = f[i - 1][0] + w[i];
    }

    int res = max(f[n][0], f[n][1]);
    cout << res << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) solution();

    return 0;
}

股票买卖 IV

定义状态表示f[i][k][0]考虑前i支股票, 并且总的交易次数不超过k并且当前状态未持仓, 同理f[i][k][1]表示当前状态持仓

定义从持仓到空仓达成了一次交易, 注意状态的初始化所有状态都是非法状态, f[0][0][0]代表考虑0支股票, 交易次数不超过0次, 并且当前空仓的最大利润, f[0][0][0] == 0, 算法时间复杂度$O(nk)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, K = 110;

int n, k, w[N];
int f[N][K][2];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    memset(f, -0x3f, sizeof f);
    f[0][0][0] = 0;

    int res = 0;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 0; j <= k; ++j) {
   
            f[i][j][0] = f[i - 1][j][0];
            if (j) {
   
                f[i][j][0] = max(f[i][j][0], f[i - 1][j - 1][1] + w[i]);
            }
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] - w[i]);
            res = max({
   res, f[i][j][0], f[i][j][1]});
        }
    }

    cout << res << '\n';
    return 0;
}

股票买卖 V

没有交易次数的限制定义状态表示f[i][0]考虑前i支股票并且当前状态是空仓, f[i][1]当前状态是持仓, f[i][2]代表当前状态是冷冻期

算法时间复杂度$O(n)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, w[N];
int f[N][3];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
   
        f[i][0] = f[i - 1][0];
        f[i][0] = max(f[i][0], f[i - 1][2]);
        f[i][1] = f[i - 1][1];
        f[i][1] = max(f[i][1], f[i - 1][0] - w[i]);
        f[i][2] = f[i - 1][1] + w[i];
    }

    int res = max({
   f[n][0], f[n][1], f[n][2]});
    cout << res << '\n';
    return 0;
}

设计密码问题

KMP算法原理: 基础数据结构模板

回顾双字符串写法的KMP算法, 不包含子串P等价于指针j移动不到位置m, 定义状态表示f[i][j]表示密码S当前第i个字符, 并且对于模式串P, 指针走到了位置j的所有方案

对于当前位置i, 有26种选择

对于模式串, j初始在位置0, 也就是在字符串的第0个前缀位置

算法时间复杂度$O(26\times N^2)$

#include <bits/stdc++.h>

using namespace std;

const int N = 55, MOD = 1e9 + 7;

int n;
string p;
int ne[N], f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> p;
    int m = p.size();

    for (int i = 1; i < m; ++i) {
   
        int j = ne[i - 1];
        while (j && p[j] != p[i]) j = ne[j - 1];
        if (p[j] == p[i]) ne[i] = j + 1;
    }

    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            for (char c = 'a'; c <= 'z'; ++c) {
   
                int idx = j;
                while (idx && p[idx] != c) idx = ne[idx - 1];
                if (p[idx] == c) idx++;

                if (idx < m) {
   
                    f[i][idx] = (f[i][idx] + f[i - 1][j]) % MOD;
                }
            }
        }
    }

    int res = 0;
    for (int i = 0; i < m; ++i) res = (res + f[n][i]) % MOD;

    cout << res << '\n';
    return 0;
}

矩阵乘法优化代码, 时间复杂度$O(m\log n)$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 55, MOD = 1e9 + 7;

int n, m;
string s;
int ne[N];
LL A[N][N];

void init() {
   
    for (int i = 1; i < m; ++i) {
   
        int j = ne[i - 1];
        while (j && s[j] != s[i]) j = ne[j - 1];
        if (s[j] == s[i]) ne[i] = j + 1;
    }

    for (int i = 0; i < m; ++i) {
   
        for (char c = 'a'; c <= 'z'; ++c) {
   
            int k = i;
            while (k && s[k] != c) k = ne[k - 1];
            if (s[k] == c) k++;
            if (k < m) A[i][k] = (A[i][k] + 1) % MOD;
        }
    }
}

void mul(LL c[], LL a[], LL b[][N]) {
   
    static LL tmp[N];
    memset(tmp, 0, sizeof tmp);

    for (int i = 0; i < m; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            tmp[i] = (tmp[i] + (LL) a[j] % MOD * b[j][i] % MOD) % MOD;
        }
    }

    memcpy(c, tmp, sizeof tmp);
}

void mul(LL c[][N], LL a[][N], LL b[][N]) {
   
    static LL tmp[N][N];
    memset(tmp, 0, sizeof tmp);

    for (int i = 0; i < m; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            for (int k = 0; k < m; ++k) {
   
                tmp[i][j] = (tmp[i][j] + (LL) a[i][k] % MOD * (LL) b[k][j] % MOD) % MOD;
            }
        }
    }

    memcpy(c, tmp, sizeof tmp);
}

void solve() {
   
    LL f0[N] = {
   0};
    f0[0] = 1;

    int k = n;
    while (k) {
   
        if (k & 1) mul(f0, f0, A);
        mul(A, A, A);
        k >>= 1;
    }

    LL ans = 0;
    for (int i = 0; i < m; ++i) ans = (ans + f0[i]) % MOD;

    ans = (ans % MOD + MOD) % MOD;
    cout << ans << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    m = s.size();
    init();
    solve();

    return 0;
}

状态压缩DP

蒙德里安的梦想问题

只摆放横着的小方格, 竖着的位置空下, 由竖着的小方格进行填充, 因此将问题转化为只摆放横向小方格纵向小方格合法的情况

使用二进制数字表示当前列的状态, 如上图, 当前状态就是1010010, 定义状态表示f[i][j]表示当前考虑第i列, 并且上一列伸出的状态是j的所有方案, 属性是cnt

假设当前枚举的状态是j, 上一层状态是k

• 上一个状态与枚举当前列状态在相同位置上不能有1, 因为是横向放置小方格, 有1会冲突, 也就是j & k == 0
• j状态所有竖方向上剩余的位置连续的空白位置数量必须是偶数, 如果是奇数, 因为只枚举横向摆放的小方块, 无法放置纵向的小方块, j | k 不存在连续奇数个0

算法时间复杂度$O(n\times 2^n)$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 12;

int n, m;
LL f[N][1 << N];
bool valid[1 << N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n >> m, n && m) {
   
        // 判断所有状态是否存在奇数个0
        for (int i = 0; i < 1 << n; ++i) {
   
            valid[i] = true;
            // 当前连续0的个数
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
   
                if (i >> j & 1) {
   
                    if (cnt & 1) valid[i] = false;
                    cnt = 0;
                }
                else cnt++;
            }
            if (cnt & 1) valid[i] = false;
        }

        memset(f, 0, sizeof f);
        // 第0列前面不能对第一列造成影响, 前一列的状态一定是0, 只有是才有一种方案
        f[0][0] = 1;
        for (int i = 1; i <= m; ++i) {
   
            for (int j = 0; j < 1 << n; ++j) {
   
                for (int k = 0; k < 1 << n; ++k) {
   
                    if ((j & k) == 0 && valid[j | k]) f[i][j] += f[i - 1][k];
                }
            }
        }

        cout << f[m][0] << '\n';
    }

    return 0;
}

去除无效状态优化

注意不能直接初始化所有状态1 << N, 假设当前n == 1, 所有高位都是非法状态

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 12;

int n, m;
LL f[N][1 << N];
bool valid[1 << N];
vector<int> ne[1 << N];

void init() {
   
    for (int i = 0; i < 1 << n; ++i) {
   
        valid[i] = true;
        int cnt = 0;
        for (int j = 0; j < n; ++j) {
   
            if (i >> j & 1) {
   
                if (cnt & 1) valid[i] = false;
                cnt = 0;
            }
            else cnt++;
        }
        if (cnt & 1) valid[i] = false;
    }

    for (int i = 0; i < 1 << n; ++i) {
   
        ne[i].clear();
        for (int j = 0; j < 1 << n; ++j) {
   
            if ((i & j) == 0 && valid[i | j]) ne[i].push_back(j);
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n >> m, n && m) {
   
        init();

        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1; i <= m; ++i) {
   
            for (int j = 0; j < 1 << n; ++j) {
   
                for (int k : ne[j]) {
   
                    f[i][j] += f[i - 1][k];
                }
            }
        }

        cout << f[m][0] << '\n';
    }

    return 0;
}

最短Hamilton路径问题

发现 $n\le 20$ 可以使用二进制状态表示当前已经走过了哪些点
定义状态表示f[i][j]表示当前走到了点i, 并且已经走过的点的集合是j的所有方案, 属性是最短哈密顿长度, 状态计算是当前点是由上一个哪个点转移过来的. 假设是k点, 那么状态转移方程就是f[i][j] = min(f[i][j], f[k][j - 1 << i] + w), 算法时间复杂度$O(n\times 2^n)$

#include <bits/stdc++.h>

using namespace std;

const int N = 21;

int n, w[N][N];
int f[N][1 << N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) w[i][i] = 0;
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < n; ++j) {
   
            cin >> w[i][j];
        }
    }

    memset(f, 0x3f, sizeof f);

    f[0][1] = 0;
    for (int j = 0; j < 1 << n; ++j) {
   
        for (int i = 0; i < n; ++i) {
   
            if (j >> i & 1) {
   
                for (int k = 0; k < n; ++k) {
   
                    if (j >> k & 1) {
   
                        f[i][j] = min(f[i][j], f[k][j - (1 << i)] + w[k][i]);
                    }
                }
            }
        }
    }

    int res = f[n - 1][(1 << n) - 1];
    cout << res << '\n';

    return 0;
}

小国王

发现国王的数量不超过$10$, 可以使用指数级别的算法, $dfs$或者状态压缩, 使用状态表示代表一类方案, 只考虑类与类之间的关系
发现当前行怎么摆, 只与上一行状态有关, 与上上行状态无关也就是影响不到当前行, 可以定义状态表示f[i][j][k], 当前摆到了第i行并且当前行的状态是j并且当前使用了$k$个国王的所有方案, 状态就是从上一行转移
算法时间复杂度$O(nk\times 2^n)$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 12, M = 1 << N;

int n, k;
int cnt[N];
LL f[N][M][N * N];
vector<int> vec;

void init() {
   
    for (int i = 0; i < 1 << n; ++i) {
   
        if (!(i & i >> 1)) {
   
            vec.push_back(i);
            for (int j = 0; j < n; ++j) cnt[i] += i >> j & 1;
        }
    }
}

bool valid(int s1, int s2) {
   
    int s = s1 | s2;
    for (int i = 0; i < n; ++i) {
   
        if ((s >> i) & (s >> i + 1)) return false;
    }
    return true;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;

    init();
    f[0][0][0] = 1;

    for (int i = 1; i <= n + 1; ++i) {
   
        for (int s1 : vec) {
   
            for (int s2 : vec) {
   
                if ((s1 & s2) || !valid(s1, s2)) continue;
                for (int l = 0; l <= k; ++l) {
   
                    int cnt1 = cnt[s1];
                    if (l >= cnt1) f[i][s1][l] += f[i - 1][s2][l - cnt1];
                }
            }
        }
    }

    cout << f[n + 1][0][k] << '\n';
    return 0;
}

玉米田

相邻的玉米田不能有公共边缘

也就是说假设当前的玉米田的绿色部分, 那么黄色的部分是不能种玉米的, 此外还有一些地方是无非法种植的
因为当前行能否摆放只与上一行有关, 定义状态表示f[i][j]表示当前摆放的是第i行, 并且当前行摆放状态是j的所有方案
假设上一行状态是t, 那么有t & j == 0, 并且当前行的状态j不能有两个连续的摆放位置

#include <bits/stdc++.h>
using namespace std;

const int N = 14, M = 1 << N, MOD = 1e8;

int n, m;
int st[N][N];
vector<int> vec;
int f[N][M];

void init() {
   
    for (int i = 0; i < 1 << m; ++i) {
   
        if ((i & (i << 1)) == 0) {
   
            vec.push_back(i);
        }
    }
}

bool valid(int idx, int s) {
   
    for (int j = 0; j < m; ++j) {
   
        if ((s >> j & 1) && !st[idx][j + 1]) {
   
            return false;
        }
    }
    return true;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            cin >> st[i][j];
        }
    }

    init();

    f[0][0] = 1;

    for (int i = 1; i <= n + 1; ++i) {
   
        for (int s1 : vec) {
   
            if (!valid(i, s1)) continue;
            for (int s2 : vec) {
   
                if (s1 & s2) continue;
                if (!valid(i - 1, s2)) continue;
                f[i][s1] = (f[i][s1] + f[i - 1][s2]) % MOD;
            }
        }
    }

    cout << f[n + 1][0] << '\n';
    return 0;
}

效率优化写法

#include <bits/stdc++.h>
using namespace std;

const int N = 14, M = 1 << N, MOD = 1e8;

int n, m;
int st[N][N];
vector<int> vec;
int f[N][M];

void init() {
   
    // 当前状态和下一个状态做and操作, 判断是否相邻两个1
    for (int i = 0; i < 1 << m; ++i) {
   
        if (i & (i << 1)) continue;
        vec.push_back(i);
    }
}

bool valid(int idx, int s) {
   
    for (int j = 0; j < m; ++j) {
   
        if ((s >> j & 1) && !st[idx][j + 1]) {
   
            return false;
        }
    }
    return true;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            cin >> st[i][j];
        }
    }

    init();

    f[0][0] = 1;

    for (int i = 1; i <= n + 1; ++i) {
   
        for (int s1 : vec) {
   
            if (!valid(i, s1)) continue;
            for (int s2 : vec) {
   
                if (s1 & s2) continue;
                if (!valid(i - 1, s2)) continue;
                f[i][s1] = (f[i][s1] + f[i - 1][s2]) % MOD;
            }
        }
    }

    cout << f[n + 1][0] << '\n';
    return 0;
}

炮兵阵地问题

当前行的摆放情况与上一行有关, 并且与上上行也有关, 因此定义状态表示f[i][s1][s2]表示当前放置第i行, 并且当前行状态是s1, 上一行状态是s2的集合, 属性是已经摆放的炮兵部队数量, 算法时间复杂度$O(n\cdot 2^m\cdot 2^m\cdot 2^m)$虽然看起来很大, 但是因为最开始的时候对所有状态进行了预处理, 实际复杂度很低

预处理时间复杂度$O(m\cdot 2^m)$, 实际运行时间$130ms$

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 12, S = 1 << M;

int n, m;
bool st[N][N];
int f[2][S][S];
vector<int> vec;
int cnt[S];

bool valid(int idx, int s) {
   
    for (int j = 0; j < m; ++j) {
   
        if ((s >> j & 1) && !st[idx][j + 1]) return false;
    }
    return true;
}

void init() {
   
    for (int i = 0; i < 1 << m; ++i) {
   
        bool tag = false;
        for (int j = 0; j < m; ++j) {
   
            int s1 = i >> j & 1;
            int s2 = i >> (j + 1) & 1;
            int s3 = i >> (j + 2) & 1;
            if (s1 & (s2 | s3)) tag = true;
        }
        if (tag) continue;
        vec.push_back(i);
        for (int j = 0; j < m; ++j) cnt[i] += i >> j & 1;
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    init();

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            char c;
            cin >> c;
            if (c == 'P') st[i][j] = true;
            else st[i][j] = false;
        }
    }

    for (int i = 1; i <= n + 2; ++i) {
   
        for (int s1 : vec) {
   
            if (!valid(i, s1)) continue;
            for (int s2 : vec) {
   
                if (!valid(i - 1, s2)) continue;
                for (int s3 : vec) {
   
                    if (s1 & s2 | s1 & s3 | s2 & s3) continue;
                    int &curr = f[i & 1][s1][s2];
                    int &pre = f[i - 1 & 1][s2][s3];
                    curr = max(curr, pre + cnt[s1]);
                }
            }
        }
    }

    cout << f[n + 2 & 1][0][0] << '\n';
    return 0;
}

愤怒的小鸟(NOI)

因为最初的小猪的坐标是给定的$(x_i,y_i)$, 又因为所有的小鸟抛物线从原点开始发射, $y=a{x}^2+bx$, 由两个小猪就能确定一条抛物线, 假设给定了$n$个小猪, 生成的抛物线数量是$O(n^2)$级别的, 并且预处理出每条抛物线能覆盖的点

问题就变成了给定$n^2$条抛物线, 问选择最少的抛物线将所有小猪覆盖, 这是典型的重复复盖问题, 最优的解法其实是$Dancing-Links$, 但是发现给定的小猪数量很少$n\le 18$, 因此可以使用状态压缩$dp$尝试解决

我们先思考如何使用$dfs$解决

$dfs$核心是搜索顺序, 使用某种顺序枚举出所有方案

$dfs$的伪代码

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int m, res;
int path[N][N];

bool valid(int x, int y, int a, int b) {
   
    
}

void dfs(int s, int cnt) {
   
    if (s == (1 << m) - 1) {
   
        res = min(res, cnt);
        return;
    }

    int c = 0;
    for (int i = 0; i < m; ++i) {
   
        if (!(s >> i & 1)) {
   
            c = i;
            break;
        }
    }
    
    // 枚举能覆盖c的抛物线
    // 假设选择抛物线能覆盖的列是s2
    dfs(s | s2, cnt + 1);
}

发现只要$s$确定的, $dfs$计算出的最小值就是确定的, 因此可以定义一个状态$f[s]$表示 覆盖的列的状态是$s$($s$是二进制数)的最少抛物线数量

具体的状态转移方程$f[s^{\prime }]=f[s]+1$

注意细节$a\ne 0$并且$a<0$, 是合法的抛物线

#include <bits/stdc++.h>

using namespace std;

typedef pair<double, double> PDD;
const int N = 20, M = 1 << N;
const double EPS = 1e-8;

int n, m;
PDD pos[N];
// 两个小猪组成的抛物线能覆盖的小猪状态
int path[N][N];
int f[M];

bool cmp(double a, double b) {
   
    return fabs(a - b) <= EPS;
}

void solution() {
   
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
   
        double x, y;
        cin >> x >> y;
        pos[i] = {
   x, y};
    }

    memset(path, 0, sizeof path);
    for (int i = 0; i < n; ++i) {
   
        path[i][i] = 1 << i;
        for (int j = 0; j < n; ++j) {
   
            auto &[x0, y0] = pos[i];
            auto &[x1, y1] = pos[j];

            if (x0 == x1) continue;
            double a = (y0 / x0 - y1 / x1) / (x0 - x1);
            double b = y0 / x0 - a * x0;
            if (a >= 0) continue;

            int s = 0;
            for (int k = 0; k < n; ++k) {
   
                auto [x2, y2] = pos[k];
                if (cmp(a * x2 * x2 + b * x2, y2)) s |= 1 << k;
            }
            path[i][j] = s;
        }
    }

    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    for (int i = 0; i < 1 << n; ++i) {
   
        int c = 0;
        for (int j = 0; j < n; ++j) {
   
            if (!(i >> j & 1)) {
   
                c = j;
                break;
            }
        }
        for (int j = 0; j < n; ++j) {
   
            int new_s = i | path[c][j];
            f[new_s] = min(f[new_s], f[i] + 1);
        }
    }

    cout << f[(1 << n) - 1] << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) solution();

    return 0;
}

宝藏(NOI)

区间DP

石子合并问题

定义状态表示f[i][j]从i合并到j的最小代价, 状态转移可以由上一步是合并哪两堆进行转移, f[i][k]和f[k + 1][j]

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i <= n; ++i) w[i] += w[i - 1];

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i <= n; ++i) f[i][i] = 0;

    for (int len = 2; len <= n; ++len) {
   
        for (int i = 1; i + len - 1 <= n; ++i) {
   
            int j = i + len - 1;
            for (int k = i; k < j; ++k) {
   
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + w[j] - w[i - 1]);
            }
        }
    }

    cout << f[1][n] << '\n';
    return 0;
}

环形石子合并问题

环状问题, 可以破环为链, 使用两个相同的链连接起来代替环
定义状态表示f[i][j]表示合并区间[i, j]的最大得分, 状态转移是上一步是如何合并的, 假设上一步是[i, k]和[k + 1, j]已经合并好了
状态转移方程$f[i][j]=\max (f[i][j],f[i][k]+f[k+1][j])$, 算法时间复杂度$O(n^3)$

#include <bits/stdc++.h>

using namespace std;

const int N = 410, INF = 0x3f3f3f3f;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
   
        cin >> w[i];
        w[i + n] = w[i];
    }

    for (int i = 1; i <= 2 * n; ++i) w[i] += w[i - 1];

    int max_val = 0, min_val = INF;

    memset(f, -0x3f, sizeof f);
    for (int len = 1; len <= n; ++len) {
   
        for (int i = 1; i + len - 1 <= 2 * n; ++i) {
   
            if (len == 1) {
   
                f[i][i] = 0;
                continue;
            }
            int j = i + len - 1;
            for (int k = i; k < j; ++k) {
   
                int val = f[i][k] + f[k + 1][j] + w[j] - w[i - 1];
                f[i][j] = max(f[i][j], val);
            }
            if (len == n) max_val = max(max_val, f[i][j]);
        }
    }

    memset(f, 0x3f, sizeof f);
    for (int len = 1; len <= n; ++len) {
   
        for (int i = 1; i + len - 1 <= 2 * n; ++i) {
   
            if (len == 1) {
   
                f[i][i] = 0;
                continue;
            }
            int j = i + len - 1;
            for (int k = i; k < j; ++k) {
   
                if (f[i][k] == INF || f[k + 1][j] == INF) continue;
                int val = f[i][k] + f[k + 1][j] + w[j] - w[i - 1];
                f[i][j] = min(f[i][j], val);
            }

            if (len == n) min_val = min(min_val, f[i][j]);
        }
    }
    
    if (n == 1) min_val = 0;
    cout << min_val << '\n' << max_val << '\n';

    return 0;
}

能量项链

因为每个珠子有两个属性, 一个是头标记一个是尾标记, 对于题目的第一个例子

实际的珠子情况是(2, 3), (3, 5), (5, 10), (10, 2), 但是我们发现使用2, 3, 5, 10, 2这几个数字就能代表这些珠子, 因此创建这样一个序列2, 3, 5, 10, 2, 3, 5, 10就能将环转化为链状

定义状态表示f[i][j], 合并[L, R]这一段的最大能量
状态转移$f[i][j]=\max (f[i][j],f[i][k]+f[k][j]+w[i]\ast w[k]\ast w[j])$
算法时间复杂度$O(n^3)$

珠子写法

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 210;

int n, w[N];
PII vals[N];
int f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    for (int i = 1; i < n; ++i) vals[i] = {
   w[i], w[i + 1]};
    vals[n] = {
   w[n], w[1]};

    for (int i = 1; i <= n; ++i) vals[i + n] = vals[i];

    memset(f, -0x3f, sizeof f);
    for (int i = 1; i <= 2 * n; ++i) f[i][i] = 0;

    int res = 0;
    for (int len = 2; len <= n; ++len) {
   
        for (int i = 1; i + len - 1 <= 2 * n; ++i) {
   
            int j = i + len - 1;
            for (int k = i; k < j; ++k) {
   
                f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + vals[i].first * vals[k].second * vals[j].second);
            }
            if (len == n) res = max(res, f[i][j]);
        }
    }

    cout << res << '\n';

    return 0;
}

优化写法

#include <bits/stdc++.h>

using namespace std;

const int N = 210;

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

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
   
        cin >> w[i];
        w[i + n] = w[i];
    }

    memset(f, -0x3f, sizeof f);

    int res = 0;
    for (int len = 1; len <= n + 1; ++len) {
   
        for (int i = 1; i + len - 1 <= 2 * n; ++i) {
   
            int j = i + len - 1;

            if (len == 2) {
   
                f[i][j] = 0;
                continue;
            }

            for (int k = i; k <= j; ++k) {
   
                f[i][j] = max(f[i][j], f[i][k] + f[k][j] + w[i] * w[k] * w[j]);
            }
            res = max(res, f[i][j]);
        }
    }

    cout << res << "\n";
    return 0;
}

加分二叉树问题

定义状态表示f[i][j]为中序遍历为[i, j]的子树的最大分数, 因为中序遍历是按照左中右的顺序, 因此可以按照当前节点是否是子树的根节点进行分类, 从而进行状态转移, 算法时间复杂度$O(n^3)$

#include <bits/stdc++.h>

using namespace std;

const int N = 35;

int n, w[N];
int f[N][N];
int path[N][N];

void dfs(int u, int v) {
   
    if (u > v) return;
    int fa = path[u][v];
    cout << fa << ' ';
    dfs(u, fa - 1);
    dfs(fa + 1, v);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    for (int i = 1; i <= n; ++i) f[i][i] = w[i], path[i][i] = i;

    for (int len = 2; len <= n; ++len) {
   
        for (int i = 1; i + len - 1 <= n; ++i) {
   
            int j = i + len - 1;
            for (int k = i; k <= j; ++k) {
   
                int l_val = k == i ? 1 : f[i][k - 1];
                int r_val = k == j ? 1 : f[k + 1][j];
                int score = l_val * r_val + w[k];
                if (score > f[i][j]) {
   
                    f[i][j] = score;
                    path[i][j] = k;
                }
            }
        }
    }

    cout << f[1][n] << '\n';
    dfs(1, n);

    return 0;
}

凸多边形的划分问题

将问题按照最后一步进行划分, 对于最后一条边$[1,7]$, 最后划分完一定属于某个三角形

因为三角形之间不能相交, 因此上面的绿色部分和粉色部分是独立的
定义状态表示f[i][j]表示划分多边形的顶点范围是[i, j]的最小权值和的集合, 属性是最小值
对于当前状态$f[1][7]=f[1][4]+f[4][7]+w[1]\ast w[4]\ast w[7]$

观察到顶点的权值是$10^9$级别, 乘积会爆$int$, 因此需要使用高精度进行计算, 算法时间复杂度$O(n^3)$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 55;

int n, w[N];
vector<int> f[N][N];

vector<int> add(vector<int> &a, vector<int> &b) {
   
    if (a.size() < b.size()) return add(b, a);

    vector<int> res;
    int c = 0;
    for (int i = 0; i < a.size(); ++i) {
   
        int val = c + a[i] + (i < b.size() ? b[i] : 0);
        res.push_back(val % 10);
        c = val / 10;
    }
    if (c) res.push_back(c);

    return res;
}

vector<int> mul(vector<int> &a, int b) {
   
    vector<int> res;

    LL c = 0;
    for (int i = 0; i < a.size(); ++i) {
   
        c += (LL) a[i] * b;
        res.push_back(c % 10);
        c /= 10;
    }

    while (c) res.push_back(c % 10), c /= 10;
    while (res.size() && res.back() == 0) res.pop_back();

    return res;
}

int cmp(vector<int> &a, vector<int> &b) {
   
    if (a.size() < b.size()) return -1;
    if (a.size() > b.size()) return 1;

    for (int i = a.size() - 1; i >= 0; --i) {
   
        if (a[i] != b[i]) {
   
            if (a[i] < b[i]) return -1;
            else return 1;
        }
    }

    return 0;
}

void set_max(vector<int> &a) {
   
    for (int i = 0; i < 128; ++i) a.push_back(9);
}

void set_zero(vector<int> &a) {
   
    a.clear();
    a.push_back(0);
}

void init() {
   
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= n; ++j) {
   
            if (i == j || j == i + 1) set_zero(f[i][j]);
            else set_max(f[i][j]);
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    for (int len = 3; len <= n; ++len) {
   
        for (int i = 1; i + len - 1 <= n; ++i) {
   
            int j = i + len - 1;
            for (int k = i + 1; k < j; ++k) {
   
                vector<int> tmp(1, 1);
                vector<int> val = add(f[i][k], f[k][j]);
                tmp = mul(tmp, w[i]);
                tmp = mul(tmp, w[k]);
                tmp = mul(tmp, w[j]);
                val = add(val, tmp);

                if (cmp(val, f[i][j]) == -1) f[i][j] = val;
            }
        }
    }

    vector<int> &res = f[1][n];
    for (int i = res.size() - 1; i >= 0; --i) cout << res[i];
    cout << '\n';

    return 0;
}

棋盘分割问题(NOI)

切n - 1刀, 分为n份, 每一个部分都会计算分值, 要求均方差最小

$$\bar{x}=\frac{{\sum }_{i=1}^n{x}_i}{n}$$

求最小值
$$\frac{{\sum }_{i=1}^n(x_i-\bar{x}{)}^2}{n}$$

整理得到最小化每一部分的平方之和的最小值
$$\frac{{\sum }_{i=1}^n{x}_i^2}{n}$$

状态表示状态计算
具体的状态转移过程, 假设当前是横向切


记忆化搜索代码

#include <bits/stdc++.h>

using namespace std;

const int N = 16, M = 9;
const double INF = 1e18;

int n;
int w[M][M], s[M][M];
double f[M][M][M][M][N];
double X;

void init() {
   
    cin >> n;
    for (int i = 1; i < M; ++i) {
   
        for (int j = 1; j < M; ++j) {
   
            cin >> w[i][j];
        }
    }

    for (int i = 1; i < M; ++i) {
   
        for (int j = 1; j < M; ++j) {
   
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + w[i][j];
        }
    }

    X = (double) s[M - 1][M - 1] / n;
}

double calc(int x1, int y1, int x2, int y2) {
   
    double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] - X;
    return sum * sum / n;
}

double dp(int x1, int y1, int x2, int y2, int k) {
   
    double &val = f[x1][y1][x2][y2][k];
    if (val >= 0) return val;
    if (k == 1) return val = calc(x1, y1, x2, y2);

    val = INF;
    // 枚举横切
    for (int i = x1; i < x2; ++i) {
   
        val = min(val, dp(x1, y1, i, y2, k - 1) + calc(i + 1, y1, x2, y2));
        val = min(val, dp(i + 1, y1, x2, y2, k - 1) + calc(x1, y1, i, y2));
    }

    // 枚举纵切
    for (int i = y1; i < y2; ++i) {
   
        val = min(val, dp(x1, y1, x2, i, k - 1) + calc(x1, i + 1, x2, y2));
        val = min(val, dp(x1, i + 1, x2, y2, k - 1) + calc(x1, y1, x2, i));
    }

    return val;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    memset(f, -1, sizeof f);

    printf("%.3lf\n", sqrt(dp(1, 1, 8, 8, n)));
    return 0;
}

树形DP

没有上司的舞会问题

定义状态表示 f[i][0]表示考虑当前以i为根节点的子树, 并且i不参加的最大值, f[i][1]表示考虑当前以i为根节点的子树, 并且i参加的最大值

如果当前节点参加, 那么子节点一定不能参加, 否则如果当前节点不参加, 子节点可以选择参加或者不参加

树形结构, 每个节点只会被访问一次, 算法时间复杂度$O(n)$

#include <bits/stdc++.h>

using namespace std;

const int N = 6010, M = N;

int n, w[N];
int head[N], ed[M], ne[M], idx;
bool st[N];
int f[N][2];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void dfs(int u) {
   
    f[u][1] = w[u];
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(head, -1, sizeof head);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    for (int i = 0; i < n - 1; ++i) {
   
        int u, fa;
        cin >> u >> fa;
        add(fa, u);
        st[u] = true;
    }

    int root = 1;
    for (int i = 1; i <= n; ++i) {
   
        if (!st[i]) {
   
            root = i;
            break;
        }
    }

    dfs(root);

    int res = max(f[root][0], f[root][1]);
    cout << res << '\n';

    return 0;
}

树的最长路径

如果是暴力的做法是枚举所有路径的起点和终点, 因为树上路径之间长度是固定的可以预处理, 算法时间复杂度$O(n^2\log n)$
将路线分类

假设定义函数$T(i)$表示, 经过点$i$的最长路, 那么结果就是$res=\max \{T(i)\}$, 如果想计算$T(i)$的最大值, 那么上述三种情况需要求最大值, 可以预处理出到达节点$i$的最大值和次大值, 记为$f(i)$和$g(i)$, 那么$T(i)=\max \{f(i),f(i)+g(i),f(p)\}$, $p$是$i$的父节点
因为每个节点考虑一遍算法时间复杂度$O(n)$

因为是树形结构, 可以使用递归解决, 父节点情况可以递归返回到父节点的时候处理

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10, M = N * 2;

int n;
int head[N], ed[M], ne[M], w[M], idx;
int f[N], g[N], res;

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

void dfs(int u, int fa) {
   
    f[u] = g[u] = 0;
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == fa) continue;
        dfs(v, u);
        if (f[v] + w[i] > f[u]) g[u] = f[u], f[u] = f[v] + w[i];
        else if (f[v] + w[i] > g[u]) g[u] = f[v] + w[i];
    }
    res = max(res, f[u] + g[u]);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }

    dfs(1, -1);

    cout << res << '\n';
    return 0;
}

树的中心(换根dp)

为什么需要换根? 因为对于当前节点$u$需要子节点$v$对当前节点的贡献, 以及父节点$fa$对当前节点的贡献


将所有经过$i$点的分为两类, 从当前节点向下的

和红色路线, 从当前节点向上的并且不走回头路的$w[i][p]+f_{max}$
因为每个节点遍历一次, 算法时间复杂度$O(n)$

关于$dfs2$过程, 不能在递归调用过程中初始化, 因为$dfs2$是从父节点向子节点更新的

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10, M = N << 1, INF = 0x3f3f3f3f;

int n;
int head[N], ed[M], ne[M], w[M], idx;
int f1[N], f2[N], g[N];
int s1[N], s2[N];

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

void dfs1(int u, int fa) {
   
    f1[u] = f2[u] = 0;
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == fa) continue;
        dfs1(v, u);
        int val = f1[v] + w[i];
        if (val >= f1[u]) {
   
            f2[u] = f1[u];
            s2[u] = s1[u];
            f1[u] = val;
            s1[u] = v;
        }
        else if (val > f2[u]) {
   
            f2[u] = val;
            s2[u] = v;
        }
    }
}

void dfs2(int u, int fa) {
   
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == fa) continue;
        if (s1[u] == v) g[v] = max(g[u], f2[u]) + w[i];
        else g[v] = max(g[u], f1[u]) + w[i];
        dfs2(v, u);
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }

    dfs1(1, -1);
    dfs2(1, -1);

    int res = INF;
    for (int i = 1; i <= n; ++i) res = min(res, max(f1[i], g[i]));

    cout << res << '\n';
    return 0;
}

数字转换

树的最长路径问题的应用
能相互转化的前提条件是约数之和小于原数字, 因为一个数字的约数之和是固定的, 假设约数之和是$y$, 原数字是$x$, 那么可以将
$y$视作$x$的父节点, 也就是说每个节点$x$的父节点是唯一的, 构成多棵树
在所有的树里面找到长度最长的路径

问题变成了如何快速的计算$[1,n]$的约数之和, 筛法的思想, 求当前数字$x$是哪些数的约数, 也就是当前数是哪些数的倍数
时间复杂度$O(n\log n)$

注意构建边的过程从$2$开始, 因为在当前定义下$1$的约数之和是$0$

#include <bits/stdc++.h>

using namespace std;

const int N = 50010, M = N << 1;

int n, s[N];
// 节点约数之和不超过N, 因此节点编号最大值不超过N
int head[N], ed[M], ne[M], w[M], idx;
bool st[N];
int f[N], g[N];
int res;

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

void dfs(int u, int fa) {
   
    st[u] = true;
    f[u] = g[u] = 0;
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == fa) continue;
        dfs(v, u);
        int val = f[v] + w[i];
        if (val > f[u]) g[u] = f[u], f[u] = val;
        else if (val > g[u]) g[u] = val;
        res = max(res, f[u] + g[u]);
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 2 * i; j <= n; j += i) {
   
            s[j] += i;
        }
    }

    for (int i = 2; i <= n; ++i) {
   
        if (s[i] < i && s[i] != 0) {
   
            add(i, s[i], 1), add(s[i], i, 1);
        }
    }

    for (int i = 1; i <= n; ++i) {
   
        if (!st[i]) dfs(i, -1);
    }

    cout << res << '\n';
    return 0;
}

二叉苹果树

本质是有依赖的背包问题
定义状态表示$f[i][j]$表示以$i$为根节点的子树, 分配边的数量是$j$的所有方案的最大价值
状态转移过程$f[u][j]=\max (f[u][j],f[u][j-k-1]+f[v][k]+w[i])$, 预留出来从子节点连接向父节点的边
算法时间复杂度$O(n\times m\times m)$

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = N << 1;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;
int f[N][N];

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u],  w[idx] = val, head[u] = idx++;
}

void dfs(int u, int fa) {
   
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == fa) continue;
        dfs(v, u);
        for (int j = m; j >= 0; --j) {
   
            for (int k = 0; k <= j - 1; ++k) {
   
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[v][k] + w[i]);
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }

    dfs(1, -1);

    cout << f[1][m] << '\n';
    return 0;
}

战略游戏

将问题化解, 定义状态表示$f[i][0]$表示考虑以$i$为根节点的子树并且当前位置不放置哨兵的集合, 存储的值是最少的士兵数, $f[i][1]$是放置哨兵
因为递归的过程是从下向上的, 因此只需要考虑子树的情况即可, 不需要考虑当前节点的父节点的放置情况, 算法时间复杂度$O(n)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1510, M = N << 1;

int n;
int head[N], ed[M], ne[M], idx;
int f[N][2];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void dfs(int u, int fa) {
   
    f[u][0] = 0, f[u][1] = 1;
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == fa) continue;
        dfs(v, u);
        f[u][0] += f[v][1];
        f[u][1] += min(f[v][0], f[v][1]);
    }
}

void solution() {
   
    memset(head, -1, sizeof head);
    memset(f, 0, sizeof f);
    idx = 0;

    for (int i = 0; i < n; ++i) {
   
        int u, cnt;
        char c;
        cin >> u >> c >> c >> cnt >> c;
        while (cnt--) {
   
            int v;
            cin >> v;
            add(u, v), add(v, u);
        }
    }

    dfs(0, -1);
    int res = min(f[0][0], f[0][1]);
    cout << res << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    while (cin >> n) solution();

    return 0;
}

皇宫看守

每个节点需要被观察
定义状态表示$f[i][0]$ 点$i$不放警卫并且被父节点观察到的最小花费
$f[i][1]$点$i$不放警卫并且被子节点看到的最小花费
$f[i][2]$是点$i$放警卫并且被自己看到的最小花费

#include <bits/stdc++.h>

using namespace std;

const int N = 1510, M = N << 1, INF = 0x3f3f3f3f;

int n, w[N];
int head[N], ed[M], ne[M], idx;
int f[N][3];
bool st[N];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void dfs(int u, int fa) {
   
    f[u][1] = INF, f[u][2] = w[u];
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == fa) continue;
        dfs(v, u);
        f[u][0] += min(f[v][1], f[v][2]);
        f[u][2] += min({
   f[v][0], f[v][1], f[v][2]});
    }

    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == fa) continue;
        int val = f[u][0] - min(f[v][1], f[v][2]) + f[v][2];
        f[u][1] = min(f[u][1], val);
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
   
        int u, val, m;
        cin >> u >> val >> m;
        w[u] = val;
        for (int j = 1; j <= m; ++j) {
   
            int v;
            cin >> v;
            add(u, v), add(v, u);
            st[v] = true;
        }
    }

    int u = 1;
    for (int i = 1; i <= n; ++i) {
   
        if (!st[i]) {
   
            u = i;
            break;
        }
    }

    dfs(u, -1);

    int res = min(f[u][1], f[u][2]);
    cout << res << '\n';
    return 0;
}

基础动态规划问题(2)