AtCoder Educational DP Contest 刷题记录

https://0xfaner.top/posts/atcoder-dp/

做题并不是一口气全做完的，所以前后可能有代码风格不一样的地方

写在前面

深感自己 DP 很弱的 Murabito 刷了点 DP 题，比赛地址戳这里。

后记：刷完后感觉自己又行了

A - Frog 1

题意

给定 个石头，第 i 个石头的高度为 。现在要求小青蛙从 1 号石头跳到 n 号石头，每次小青蛙可以选择从 i 号石头跳到 i+1 或 i+2 号石头，代价是起跳点与落点的高度差的绝对值。询问你最小代价。

解法

令 f[i] 表示小青蛙跳到第 i 号石头时的最小代价。

时间复杂度 #card=math&code=O%28n%29&id=QLTL3)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    vector<int> dp(n, 0), h(n);
    for (auto &x : h) cin >> x;
    for (int i = 1; i < n; ++i) {
        dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]),
                    i > 1 ? dp[i - 2] + abs(h[i] - h[i - 2]) : INT_MAX);
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

B - Frog 2

题意

给定 n 个石头与 k 的操作范围，第 i 个石头的高度为 hi。现在要求小青蛙从 1 号石头跳到 n 号石头，每次小青蛙可以选择从 i 号石头跳到 i+s ( 1≤s≤k )号石头，代价是起跳点与落点的高度差的绝对值。询问你最小代价。

解法

令 f[i] 表示小青蛙跳到第 i 号石头时的最小代价。

时间复杂度 #card=math&code=O%28nk%29&id=eDfkA)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> dp(n, 0), h(n);
    for (auto &x : h) cin >> x;
    for (int i = 1; i < n; ++i) {
        dp[i] = INT_MAX;
        for (int j = 1; j <= k && (i - j >= 0); ++j)
            dp[i] = min(dp[i], abs(h[i] - h[i - j]) + dp[i - j]);
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

C - Vacation

题意

给定太郎的暑假时长为 n 天，每天他可以进行三种活动中的一种，每种活动给他带来的愉悦值各不相同。

如果当天进行过某一种活动，第二天即不能进行另一种活动，询问太郎能获得的最大愉悦值。

解法

令 分别记录在第 i 天选做第 j 件娱乐活动的最大愉悦值。

时间复杂度 #card=math&code=O%28n%29&id=oaWqr)

代码

// RioTian 21/03/16#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int dp[N][3], a[N][3], n;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int k = 1; k <= n; ++k)
        for (int i = 0; i < 3; ++i) cin >> a[k][i];
    for (int k = 1; k <= n; ++k)
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < 3; ++j)
                if (i != j) dp[k][i] = max(dp[k][i], dp[k - 1][j] + a[k][j]);
    cout << max(dp[n][0], max(dp[n][1], dp[n][2]));
    return 0;
}

D - Knapsack 1

题意

给定太郎拥有的 n 个物品，第 i 件物品大小为 wi 权重为 vi。

给定太郎的背包的最大容量 m，询问太郎能取得的最大权重和。

解法

01 背包求解。

f[i] 表示装总大小不超过 i 的物品后的最大权重和。

时间复杂度 #card=math&code=O%28nm%29&id=KP9l3)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100010;
ll dp[N];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1, w, v; i <= n; ++i) {
        cin >> w >> v;
        for (int j = m; j >= w; j--) dp[j] = max(dp[j], dp[j - w] + v);
    }
    cout << dp[m];
    return 0;
}

E - Knapsack 2

题意

给定太郎拥有的 n 个物品，第 i 件物品大小为 权重为 。

给定太郎的背包的最大容量 m，询问太郎能取得的最大权重和。

解法

发现权值不超过 100，令 f[i] 表示装填价值为 i 的物品的最小权值。

时间复杂度 #card=math&code=O%28nv%29&id=FkLtd)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100010;
ll dp[N];
int n, m;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    cin >> n >> m;
    for (int i = 1, w, v; i <= n; ++i) {
        cin >> w >> v;
        for (int j = N - 1; j >= v; --j) dp[j] = min(dp[j], dp[j - v] + w);
    }
    int add = N - 1;
    while (dp[add] > m) add--;
    cout << add << "\n";
    return 0;
}

F - LCS

题意

给定两个字符串 s 和 t，询问它们的任意一个最长公共子串。

解法

令 表示 s 的长度为 i 的前缀和 t 的长度为 j 的前缀的最长公共子串。

递归输出即可。

时间复杂度 #card=math&code=O%28n%29&id=j04yq)

代码

#include <bits/stdc++.h>
using namespace std;
#define N 3002
char s[N], t[N];
int dp[N][N], n, m;
void print(int x, int y) {
    if (!x || !y) return;
    if (s[x] == t[y]) {
        print(x - 1, y - 1);
        putchar(s[x]);
    } else {
        (dp[x][y] == dp[x][y - 1] ? y : x)--;
        print(x, y);
    }
}
int main() {
    scanf("%s%s", s + 1, t + 1);
    int n = strlen(s + 1), m = strlen(t + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]));
        }
    print(n, m);
    return 0;
}

G - Longest Path

题意

给定一个 DAG，求其最长路径。

解法

按照 DFS 序 DP，f[i] 表示从 i 号点出发的最长路径上点的数量。

时间复杂度 #card=math&code=O%28n%29&id=zvgSi)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const int M = 1e5 + 5;
int head[N], nx[M], e[M];
int f[N], v[N], n, m;
int dfs(int x) {
    if (f[x]) return f[x];
    for (int i = head[x]; i; i = nx[i]) f[x] = max(f[x], dfs(e[i]));
    return ++f[x];
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for (int i = 1, Num = 0, x, y; i <= m; ++i) {
        cin >> x >> y;
        nx[++Num] = head[x], head[x] = Num, e[Num] = y;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, dfs(i));
    cout << ans - 1 << "\n";
    return 0;
}

H - Grid 1

题意

给定一个 的网格，太郎起始在 #card=math&code=%281%2C1%29&id=q03Dy)，最终要到达 #card=math&code=%28n%2Cm%29&id=mtwCm)。每次太郎可以从 #card=math&code=%28i%2Cj%29&id=xwqbz) 到达 #card=math&code=%28i%2Cj%2B1%29&id=i6dEn) 或 #card=math&code=%28i%2B1%2Cj%29&id=Ix03L)，其中部分格子无法达到。

询问太郎的移动方案数。

解法

表示从 #card=math&code=%281%2C1%29&id=wE2tF) 出发到达 #card=math&code=%28i%2Cj%29&id=XBS7t) 的移动方案。

时间复杂度 #card=math&code=O%28nm%29&id=mGVbe)

代码

const int N   = 1e3 + 10;
const int mod = 1e9 + 7;
vector<string> vs(N);
int dp[N][N] = {0};
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> vs[i];
    dp[0][0] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            if (i == 0 and j == 0) continue;
            if (i - 1 >= 0 && vs[i - 1][j] == '.') dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
            if (j - 1 >= 0 && vs[i][j - 1] == '.') dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;
        }
    cout << dp[n - 1][m - 1] << "\n";
}

I - Coins

题意

给定 个硬币，扔第 个硬币时，它正面朝上的概率为 。

询问对每一个硬币扔一次，正面朝上的数量多余反面朝上的硬币的数量的概率。

保证 为奇数。

解法

定义 表示前 i 个硬币中 j 个正面朝上的概率。

时间复杂度 #card=math&code=O%28n%5E2%29&id=Dw6yQ)

代码

#include <bits/stdc++.h>using namespace std;#define N 3001double f[N][N] = {1}, p[N];int n;int main() {    cin >> n;    for (int i = 1; i <= n; i++) {        cin >> p[i];        f[i][0] = f[i - 1][0] * (1 - p[i]);        for (int j = 1; j <= i; j++)            f[i][j] = f[i - 1][j - 1] * p[i] + f[i - 1][j] * (1 - p[i]);    }    double ans = 0;    for (int i = n / 2 + 1; i <= n; i++) ans += f[n][i];    cout << fixed << setprecision(10) << ans << "\n";    return 0;}

J - Sushi

题意

给定 盘寿司，每盘里有 到 个寿司。每次太郎随机选中一盘寿司，若该盘中有寿司，则吃掉一个。

询问你太郎的期望选择次数。

解法

看起来很像概率DP，但记忆化搜索即可。

表示 x 盘 1 个寿司，y 盘 2 个寿司，z 盘 3 个寿司时的期望选择次数。

时间复杂度 #card=math&code=O%28n%5E3%29&id=bzp5Q)

代码

const int N = 310;int num[4], n;double p[N][N][N];double P(int x, int y, int z) {    if (p[x][y][z] >= 0) return p[x][y][z];    double sum = (double)n / (x + y + z);    if (x) sum += P(x - 1, y, z) * x / (x + y + z);    if (y) sum += P(x + 1, y - 1, z) * y / (x + y + z);    if (z) sum += P(x, y + 1, z - 1) * z / (x + y + z);    return p[x][y][z] = sum;}void solve() {    for (int i = 0; i < N; ++i)        for (int j = 0; j < N; ++j)            for (int k = 0; k < N; ++k) p[i][j][k] = -1;    cin >> n;    p[0][0][0] = 0;    for (int i = 1, x; i <= n; ++i)        cin >> x, num[x]++;    cout << fixed << setprecision(10) << P(num[1], num[2], num[3]);}

K - Stones

题意

给定一个集合 并给定一个石堆，包含 个石子。

太郎和次郎轮流进行博弈，太郎先行。每次他们可以选择集合 中的一个数字 ，并从该石堆中取走 个石子。

无法取走石子的人为输家，询问你赢家是谁。

解法

令 表示当前剩余 个石子时先手的胜败状态。

时间复杂度 #card=math&code=O%28k%29&id=UvZ1H)

代码

这道题很奇怪，在 1 100000 1 这组数据竟然会输出不出来，但又过了，懵逼ing.

const int N = 110, M = 100000 + 10;int a[N], dp[M]      = {-1}, n, k;int check(int num) {    if (dp[num]) return dp[num];    bool flag = false;    for (int i = 1; i <= n; i++)        if (a[i] <= num && check(num - a[i]) == -1) flag = true;    return dp[num] = (flag ? 1 : -1);}void solve() {    cin >> n >> k;    for (int i = 1; i <= n; ++i) cin >> a[i];    cout << (check(k) == 1 ? "First" : "Second");}

L - Deque

题意

给定一个序列 ，太郎和次郎轮流进行博弈，太郎先行。

每次可以从序列的两端中任取一端，删去那一段的第一个元素，并获取等量的分数。

太郎和次郎都希望能最大化自己与对面的得分差，询问你最终太郎与次郎的得分差。

解法

令 表示剩余区间为 时的最大得分差。

时间复杂度 #card=math&code=O%28n%5E2%29&id=rpftT)

代码

using ll    = long long;const int N = 3e3 + 10;int n, a[N];ll dp[N][N];void solve() {    cin >> n;    for (int i = 1; i <= n; ++i) cin >> a[i];    bool f = true;    for (int i = 1; i <= n; ++i) cin >> a[i], dp[i][i] = a[i];    for (int len = 1; len <= n; ++len)        for (int i = 1; i + len <= n; ++i) {            int j    = i + len;            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]);        }    cout << dp[1][n];}

M - Candies

题意

给定 n 个小朋友的需求，第 i 个小朋友的需求为 ai，表示他可以接受 [0,ai] 个糖果。

给定 m 个糖果，要求你把这些糖果一个不剩的分配出去，询问你有多少种分配方案。

解法

表示分配完前 i 个小朋友后还剩 j 个糖果的方案。

时间复杂度 #card=math&code=O%28n%5E2%29&id=HILIJ)

代码

const int mod = 1e9 + 7, N = 110, M = 1e5 + 10;int f[N][M], s[N][M];void solve() {    int n, k;    cin >> n >> k;    f[0][k] = s[0][k] = 1;    for (int i = 1, x; i <= n; ++i) {        cin >> x;        for (int j = 1; j <= k; ++j)            f[i][j] = (s[i - 1][min(k, j + x)] - s[i - 1][j - 1] + mod) % mod;        s[i][0] = f[i][0] = s[i - 1][x];        for (int j = 1; j <= k; ++j) s[i][j] = (s[i][j - 1] + f[i][j]) % mod;    }    cout << f[n][0] << "\n";}

N - Slimes

区间DP

题意

给定 n 个史莱姆，每个史莱姆的初始大小为 。

这 n 个史莱姆站成一排。每次可以将相邻的两个史莱姆合并为一个，新的史莱姆大小为原来两个史莱姆的大小之和。合并的代价是新史莱姆的大小，询问将这 n 个史莱姆合并为 1 个的最小代价。

解法

表示将区间 [l,r] 的史莱姆合并为 1 个史莱姆的最小代价。

时间复杂度 #card=math&code=O%28n%5E3%29&id=ajmRU)

代码

using ll    = long long;const int N = 410;ll f[N][N], s[N][N];int a[N], n;void solve() {    memset(f, 0x3f, sizeof(f));    cin >> n;    vector<ll> a(n + 1);    for (int i = 1; i <= n; ++i) {        cin >> a[i];        f[i][i] = 0, s[i][i] = a[i];    }    for (int i = 1; i <= n; i++)        for (int j = i + 1; j <= n; j++) s[i][j] = s[i][j - 1] + a[j];    for (int len = 1; len < n; ++len)        for (int i = 1; i + len <= n; ++i) {            int j = i + len;            for (int k = i; k < j; ++k)                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[i][j]);        }    cout << f[1][n] << "\n";}

另外一种写法

void solve() {    int n;    cin >> n;    vector<ll> v(n + 1), sum(n + 1);    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1));    for (int i = 1; i <= n; i++) cin >> v[i], sum[i] = sum[i - 1] + v[i];    for (int i = 1; i < n; i++)        for (int j = 1; j + i <= n; j++) {            dp[j][j + i] = 1e18;            for (int k = j; k < j + i; k++)                dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k + 1][j + i]);            dp[j][j + i] += sum[j + i] - sum[j - 1];        }    cout << dp[1][n] << '\n';}

O - Matching

题意

给定 n 男 n 女，以及任意一对男女之间是否匹配。

询问有多少种方法将这男女完全配对。

解法

令 num(i) 表示 i 的二进制展开中 1 的数量。

f[i] 表示前 num(i) 个男生与状态为 i 的女生配对的方案数。

时间复杂度 #card=math&code=O%282n%C3%97n%29&id=p2fSV)

代码

#include <bits/stdc++.h>using namespace std;#define mod 1000000007#define N 22int a[N][N], f[1 << N] = {1}, n;int main() {    scanf("%d", &n);    for (int i = 1; i <= n; i++)        for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);    for (int s = 0; s < (1 << n); s++) {        int i = __builtin_popcount(s);        for (int j = 1; j <= n; j++)            if (s & (1 << (j - 1)) && a[i][j])                f[s] = (f[s] + f[s ^ (1 << (j - 1))]) % mod;    }    printf("%d\n", f[(1 << n) - 1]);    return 0;}

P - Independent Set

题意

给定一颗树，可以把树上的每一个节点染色为黑色或白色，但不允许两个相邻的节点同时为黑色。

询问染色方案数。

解法

f1[i] 表示 i 为白色时以 i 为根节点的子树的染色方案。

f2[i] 表示 i 为黑色时以 i 为根节点的子树的染色方案。

时间复杂度 O(n)

代码

#include <bits/stdc++.h>using namespace std;#define mod 1000000007#define ll long long#define N 100001#define M 200001int hd[N], nx[M], e[M], n;ll f1[N], f2[N];void dfs(int x, int fa) {    f1[x] = f2[x] = 1;    for (int i = hd[x]; i; i = nx[i])        if (e[i] != fa) {            dfs(e[i], x);            f1[x] = f1[x] * (f1[e[i]] + f2[e[i]]) % mod;            f2[x] = f2[x] * f1[e[i]] % mod;        }}int main() {    scanf("%d", &n);    for (int i = 1, Num = 0, x, y; i < n; i++) {        scanf("%d%d", &x, &y);        nx[++Num] = hd[x], hd[x] = Num, e[Num] = y;        nx[++Num] = hd[y], hd[y] = Num, e[Num] = x;    }    dfs(1, 0);    printf("%lld\n", (f1[1] + f2[1]) % mod);    return 0;}

R - Walk

题意

给定一个 n 个节点的有向图的邻接矩阵，求该有向图中长度为 k 的路径长。

解法

答案即为该邻接矩阵的 k 次幂的行列式。

使用矩阵快速幂即可，时间复杂度 O(n2log⁡k)

代码

#include <bits/stdc++.h>using namespace std;#define mod 1000000007#define ll long longll n, k;struct Matrix {    ll mat[50][50];    void clear() { memset(mat, 0, sizeof(mat)); }    void reset(int n) {        clear();        for (int i = 0; i < n; i++) mat[i][i] = 1;    }} a;Matrix MatrixMul(Matrix x, Matrix y) {    Matrix a;    a.clear();    for (int i = 0; i < n; i++)        for (int k = 0; k < n; k++)            for (int j = 0; j < n; j++)                a.mat[i][j] = (a.mat[i][j] + x.mat[i][k] * y.mat[k][j]) % mod;    return a;}ll MatrixQpow(Matrix a, ll P) {    Matrix s;    s.reset(n);    while (P) {        if (P & 1) s = MatrixMul(s, a);        a = MatrixMul(a, a), P >>= 1;    }    ll sum = 0;    for (int i = 0; i < n; i++)        for (int j = 0; j < n; j++) sum = (sum + s.mat[i][j]) % mod;    return sum;}int main() {    scanf("%lld%lld", &n, &k);    for (int i = 0; i < n; i++)        for (int j = 0; j < n; j++) scanf("%lld", &a.mat[i][j]);    printf("%lld\n", MatrixQpow(a, k));    return 0;}

S - Digit Sum

题意

给定一个数字 n 与数字 d，询问你 1 到 n 中多少数的数位和为 d 的倍数。

解法

简单数位 DP 即可，f[i][j] 表示 i 位数中，前缀对 d 取模为 j 的情况下的数位和为 d 的倍数的数的数量。

令 m 表示 n 的位数，时间复杂度 O(md)

代码

#include <bits/stdc++.h>using namespace std;#define ll long long#define mod 1000000007#define N 10001int a[N], d;ll f[N][101];ll dfs(int len, int pre, int top) {    if (!len) return pre == 0;    if (!top && f[len][pre] != -1) return f[len][pre];    int up = top ? a[len] : 9;    ll num = 0;    for (int i = 0; i <= up; i++)        num = (num + dfs(len - 1, (pre + i) % d, top && (i == up))) % mod;    if (!top) f[len][pre] = num;    return num;}char c[N];int main() {    memset(f, -1, sizeof(f));    scanf("%s%d", c + 1, &d);    int n = strlen(c + 1);    for (int i = n, j = 1; i; i--, j++) a[j] = c[i] - '0';    cout << (dfs(n, 0, 1) - 1 + mod) % mod << endl;    return 0;}

T - Permutation

题意

给定一个长度为 n−1 的仅包含 < 和 > 的字符串，第 i 位字符表示 a[i] 与 a[i+1] 的大小关系。

询问能构造多少长度为 n 的，满足该字符串的要求，且恰好包含 1 到 n 每个数一次的序列。

解法

f[i][j] 表示安排完前 i 个数且第 i 个数为 j 的方案数。

时间复杂度 O(n2)

代码

#include <bits/stdc++.h>#define ll long long#define mod 1000000007#define N 3002int f[N][N], n, ans;char c[N];int main() {    scanf("%d%s", &n, c + 1);    f[1][1] = 1;    for (int i = 2; i <= n; i++) {        if (c[i - 1] == '<')            for (int j = 2; j <= i; j++)                f[i][j] = (f[i][j - 1] + f[i - 1][j - 1]) % mod;        else            for (int j = i - 1; j; j--)                f[i][j] = (f[i][j + 1] + f[i - 1][j]) % mod;    }    for (int i = 1; i <= n; ++i) ans = (ans + f[n][i]) % mod;    printf("%d\n", ans);    return 0;}

U - Grouping

题意

给定 n 个兔子之间的匹配程度，太郎想要把这 n 只兔子分组，对于任意两只分到同一组的兔子，太郎将会获得它们两对应的匹配程度的得分。

询问太郎的最大得分。

解法

令 sum[i] 表示状态为 i 的兔子分为一组时的得分。

f[i] 表示将状态为 i 的兔子分好组的最大得分。

时间复杂度 O(2n×n)

代码

#include <bits/stdc++.h>using namespace std;#define ll long long#define M 65536#define N 16int a[N][N], v[N], n;ll sum[M], f[M];int main() {    scanf("%d", &n);    for (int i = 0; i < n; i++)        for (int j = 0; j < n; j++) scanf("%d", &a[i][j]);    for (int t = 0; t < (1 << n); t++) {        int num = 0;        for (int i = 0; i < n; i++)            if (t >> i & 1ll) v[num++] = i;        ll s = 0;        for (int i = 0; i < num; i++)            for (int j = i + 1; j < num; j++) s += a[v[i]][v[j]];        f[t] = sum[t] = s;    }    for (int i = 0; i < (1 << n); i++)        for (int j = i; j; j = (j - 1) & i) f[i] = max(f[i], f[i ^ j] + sum[j]);    printf("%lld\n", f[(1 << n) - 1]);    return 0;}

V - Subtree

题意

给定一颗 n 个节点的树，将其每个节点染成黑色或白色，要求任意两个黑色节点之间的路径上无白色节点。

询问对于每一个节点，若它为黑色，则有多少染色方案数。

解法

考虑到模数可能为合数，因此无法用乘法逆元，对每一个节点单独计算它的子树的前缀乘积与后缀乘积。

s1[i] 表示 i 号节点为黑色时，它的子树节点的染色方案。

s2[i] 表示 i 号节点为黑色时，非它的子树节点的染色方案。

第一次用vector写树形 DP，学到许多。

时间复杂度 O(n)

代码

#include <bits/stdc++.h>using namespace std;#define ll long long#define N 100001vector<int> G[N];vector<ll> a[N], b[N];ll f[N], len[N], m;ll s1[N], s2[N] = {0, 1};void dfs1(int x) {    G[x].erase(remove(G[x].begin(), G[x].end(), f[x]), G[x].end());    len[x] = G[x].size() - 1;    a[x].resize(len[x] + 1), b[x].resize(len[x] + 1);    ll sa = 1, sb = 1;    for (int i = 1; i <= len[x]; i++) {        f[G[x][i]] = x;        dfs1(G[x][i]);        a[x][i] = sa = sa * (s1[G[x][i]] + 1) % m;    }    for (int i = len[x]; i; i--) b[x][i] = sb = sb * (s1[G[x][i]] + 1) % m;    s1[x] = sa;}void dfs2(int x) {    for (int i = 1; i <= len[x]; i++) {        s2[G[x][i]] = s2[x];        if (i > 1) s2[G[x][i]] = s2[G[x][i]] * a[x][i - 1] % m;        if (i < len[x]) s2[G[x][i]] = s2[G[x][i]] * b[x][i + 1] % m;        s2[G[x][i]]++;        dfs2(G[x][i]);    }}int main() {    int n;    scanf("%d%lld", &n, &m);    for (int i = 1; i <= n; i++) G[i].push_back(-1);    for (int i = 1, x, y; i < n; i++) {        scanf("%d%d", &x, &y);        G[x].push_back(y), G[y].push_back(x);    }    dfs1(1), dfs2(1);    for (int i = 1; i <= n; i++) printf("%lld\n", s1[i] * s2[i] % m);    return 0;}

W - Intervals

题意

给定 m 个区间 [1,n] 的子区间。要求你构造出一个长度为 n 且只包含 0 和 1 的字符串，使得得分尽可能大。询问你最大得分。

得分计算方式为：若该字符串中第 i 位为 1 ，那么得分加上所有包括 i 的区间对应的权值。

解法

令 f[i] 表示安排完前 i 位，且第 i 位为 1 时的最大值。线段树优化转移。

后来发现无需存储 f[i]，只需区间加值与维护全局最值的线段树即可。

时间复杂度 O(nlog⁡n)

代码

#include <bits/stdc++.h>using namespace std;#define ll long long#define N 200001ll s[N << 2], t[N << 2];vector<pair<int, int> > a[N];void add(int x, int L, int R, int l, int r, ll c) {    if (l <= L && R <= r) return (void)(s[x] += c, t[x] += c);    int mid = (L + R) >> 1;    if (l <= mid) add(x << 1, L, mid, l, r, c);    if (r > mid) add(x << 1 | 1, mid + 1, R, l, r, c);    s[x] = max(s[x << 1], s[x << 1 | 1]) + t[x];}int n, m;int main() {    scanf("%d%d", &n, &m);    for (int i = 1, x, y, z; i <= m; i++) {        scanf("%d%d%d", &x, &y, &z);        a[y].emplace_back(x, z);    }    for (int i = 1; i <= n; i++) {        add(1, 1, n, i, i, s[1]);        for (auto &it : a[i]) add(1, 1, n, it.first, i, it.second);    }    printf("%lld\n", max(s[1], 0ll));    return 0;}

X - Tower

题意

给定 n 个方块，每个方块有三个属性：重量 w 、强度 s 与价值 v。

太郎想要选择价值总和尽可能大的一些方块摞在一起，但是每个方块上方的方块的总质量不能超过该方块的强度。

询问太郎能取得的最大价值。

解法

容易发现从上向下放更容易考虑，于是首先应该放承重能力差且重量小的方块在上面，但是这种关系仅是一种偏序关系，需要拓展为全序关系。

假定现在已经堆叠了重量为 W 的方块，在下面要放下 i 与 j 两个方块，且最佳策略是 i 在上。那么有

si<W+wj

sj≥W+wi

化简得

si+wi<sj+wj

这样就确定了对于任意两个物品的上下位置的全序关系了。

问题化简为简单的背包，时间复杂度 O(n(w+s+log⁡n))

代码

#include <bits/stdc++.h>using namespace std;#define ll long long#define M 20001#define N 1001struct faner {    int w, s, v;} a[N];ll f[M], ans;bool cmp(faner a, faner b) { return a.s + a.w < b.s + b.w; }int n;int main() {    scanf("%d", &n);    for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].w, &a[i].s, &a[i].v);    sort(a + 1, a + n + 1, cmp);    for (int i = 1; i <= n; i++)        for (int j = M - 1; j >= a[i].w; j--)            if (a[i].s + a[i].w >= j) f[j] = max(f[j], f[j - a[i].w] + a[i].v);    for (int i = 1; i < M; i++) ans = max(ans, f[i]);    printf("%lld\n", ans);    return 0;}

Y - Grid 2

题意

给定一个网格的高度 n 与宽度 m，与网格中的 k 个障碍。太郎起始在 (1,1)，最终要到达 (n,m)。每次太郎可以从 (i,j) 到达 (i,j+1) 或 (i+1,j)。其中障碍格子无法达到。

询问太郎的移动方案数。

解法

容斥原理，用无障碍情况下的方案数减去经过障碍的方案数即可。

时间复杂度 O(n+m+k2)

代码

#include <bits/stdc++.h>using namespace std;#define mod 1000000007#define ll long long#define N 200001int n, m, num;ll f[N] = {1}, fac[N] = {1}, ifac[N] = {1}, inv[N] = {1, 1};ll Calc(int n, int k) { return fac[n] * ifac[k] % mod * ifac[n - k] % mod; }struct faner {    int x, y;} a[N] = {1, 1};bool cmp(faner a, faner b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }int main() {    scanf("%d%d", &n, &m);    for (int i = 2; i <= n + m; i++)        inv[i] = (mod - mod / i) * inv[mod % i] % mod;    for (int i = 1; i <= n + m; i++)        fac[i] = fac[i - 1] * i % mod, ifac[i] = ifac[i - 1] * inv[i] % mod;    scanf("%d", &num);    for (int i = 1; i <= num; i++) scanf("%d%d", &a[i].x, &a[i].y);    sort(a + 1, a + 1 + num, cmp);    a[++num] = {n, m};    for (int i = 0; i < num; i++) {        for (int j = i + 1; j <= num; j++) {            if (a[i].y > a[j].y) continue;            ll sum = Calc(a[j].x - a[i].x + a[j].y - a[i].y, a[j].x - a[i].x);            f[j] = (mod + f[j] - f[i] * sum % mod) % mod;        }    }    printf("%lld\n", (mod - f[num]) % mod);    return 0;}

Z - Frog 3

题意

给定 n 个石头，第 i 个石头的高度为 hi。现在要求小青蛙从 1 号石头跳到 n 号石头，每次小青蛙可以选择从 i 号石头跳到 i+s ( 1≤s≤n−i )号石头，代价是起跳点与落点的高度差的平方加上一个常数 C。询问你最小代价。

解法

可以发现当高差过大时，采取中间跳板会使策略更优，高差小时则应当直接跳。

于是维护一个单调队列，保存多个跳板，每次取最优策略即可。

时间复杂度 O(n)

代码

#include <bits/stdc++.h>using namespace std;#define ll long long#define N 200001ll q[N] = {0, 1}, f[N], h[N], n, c;double slope(int i, int j) {    return (f[i] - f[j] + h[i] * h[i] - h[j] * h[j]) / 2.0 / (h[i] - h[j]);}main() {    scanf("%lld%lld", &n, &c);    for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);    int l = 1, r = 1;    for (int i = 2; i <= n; i++) {        while (l < r && slope(q[l], q[l + 1]) <= h[i]) l++;        f[i] = f[q[l]] + (h[i] - h[q[l]]) * (h[i] - h[q[l]]) + c;        while (l < r && slope(q[r - 1], q[r]) >= slope(q[r], i)) r--;        q[++r] = i;    }    printf("%lld\n", f[n]);    return 0;}

评价

AtCoder的这套 DP 题知识点涵盖广泛，题面描述清晰，题目质量很高，很值得入门选手尝试。