AtCoder Educational DP Contest 刷题记录

本文记录了 0xfaner 在 AtCoder 的 DP 专题题解

写在前面

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

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

A - Frog 1

题意

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

解法

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

时间复杂度 $ \mathcal{O}(n) $

代码

#include <bits/stdc++.h>
using namespace std;
#define N 100001
int h[N], f[N], n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    f[2] = abs(h[1] - h[2]);
    for (int i = 3; i <= n; i++)
        f[i] = min(abs(h[i] - h[i - 1]) + f[i - 1],
                   abs(h[i] - h[i - 2]) + f[i - 2]);
    printf("%d\n", f[n]);
    return 0;
}

B - Frog 2

题意

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

解法

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

时间复杂度 $ \mathcal{O}(nk) $

代码

#include <bits/stdc++.h>
using namespace std;
#define N 100001
int h[N], f[N], n, k;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    for (int i = 2; i <= n; i++) {
        int minn = 2147483647;
        for (int j = max(1, i - k); j < i; j++)
            minn = min(minn, abs(h[i] - h[j]) + f[j]);
        f[i] = minn;
    }
    printf("%d\n", f[n]);
    return 0;
}

C - Vacation

题意

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

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

解法

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

时间复杂度 $ \mathcal{O}(n) $

代码

#include <bits/stdc++.h>
using namespace std;
#define N 100001
int s[N][3], f[N][3], n;
int main() {
    scanf("%d", &n);
    for (int k = 1; k <= n; k++)
        for (int i = 0; i < 3; i++) scanf("%d", &s[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) f[k][i] = max(f[k][i], f[k - 1][j] + s[k][i]);
    printf("%d\n", max(max(f[n][0], f[n][1]), f[n][2]));
    return 0;
}

D - Knapsack 1

题意

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

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

解法

$ 01 $ 背包求解。

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

时间复杂度 $ \mathcal{O}(nm) $

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100001
ll f[N];
int n, m;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, w, v; i <= n; i++) {
        scanf("%d%d", &w, &v);
        for (int j = m; j >= w; j--) f[j] = max(f[j], f[j - w] + v);
    }
    printf("%lld\n", f[m]);
    return 0;
}

E - Knapsack 2

题意

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

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

解法

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

时间复杂度 $ \mathcal{O}(nv) $

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100001
ll f[N];
int n, m;
int main() {
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1, w, v; i <= n; i++) {
        scanf("%d%d", &w, &v);
        for (int j = N - 1; j >= v; j--) f[j] = min(f[j], f[j - v] + w);
    }
    int add = N - 1;
    while (f[add] > m) add--;
    printf("%d\n", add);
    return 0;
}

F - LCS

题意

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

解法

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

递归输出即可。

时间复杂度 $ \mathcal{O}(n) $

代码

#include <bits/stdc++.h>
using namespace std;
#define N 3002
char s[N], t[N];
int f[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 {
        (f[x][y] == f[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]) f[i][j] = f[i - 1][j - 1] + 1;
            f[i][j] = max(f[i][j], max(f[i - 1][j], f[i][j - 1]));
        }
    print(n, m);
    return 0;
}

G - Longest Path

题意

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

解法

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

时间复杂度 $ \mathcal{O}(n) $

代码

#include <bits/stdc++.h>
using namespace std;
#define N 100001
#define M 100001
int hd[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 = hd[x]; i; i = nx[i]) f[x] = max(f[x], dfs(e[i]));
    return ++f[x];
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, Num = 0, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        nx[++Num] = hd[x], hd[x] = Num, e[Num] = y;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dfs(i));
    printf("%d\n", ans - 1);
    return 0;
}

H - Grid 1

题意

给定一个 $ n \times m $ 的网格，太郎起始在 $ (1,1) $ ，最终要到达 $ (n,m) $ 。每次太郎可以从 $ (i,j) $ 到达 $ (i,j+1) $ 或 $ (i+1,j) $ ，其中部分格子无法达到。

询问太郎的移动方案数。

解法

$ f[i][j] $ 表示从 $ (1,1) $ 出发到达 $ (i,j) $ 的移动方案。

时间复杂度 $ \mathcal{O}(nm) $

代码

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

I - Coins

题意

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

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

保证 $ n $ 为奇数。

解法

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

时间复杂度 $ \mathcal{O}(n^2) $

代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define N 3001
double f[N][N] = {1}, p[N];
int n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &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];
    printf("%.10lf\n", ans);
    return 0;
}

J - Sushi

题意

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

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

解法

记忆化搜索即可。

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

时间复杂度 $ \mathcal{O}(n^3) $

代码

#include <bits/stdc++.h>
using namespace std;
#define N 301
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;
}
int main() {
    scanf("%d", &n);
    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;
    p[0][0][0] = 0;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        num[x]++;
    }
    printf("%.10lf\n", P(num[1], num[2], num[3]));
    return 0;
}

K - Stones

题意

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

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

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

解法

令 $ f[i] $ 表示当前剩余 $ i $ 个石子时先手的胜败状态。

时间复杂度 $ \mathcal{O}(k) $

代码

#include <bits/stdc++.h>
using namespace std;
#define N 101
#define M 100001
int a[N], f[M] = {-1}, n, m;
int search(int num) {
    if (f[num]) return f[num];
    bool flag = false;
    for (int i = 1; i <= n; i++)
        if (a[i] <= num && search(num - a[i]) == -1) flag = true;
    return f[num] = (flag ? 1 : -1);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    puts(search(m) == 1 ? "First" : "Second");
    return 0;
}

L - Deque

题意

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

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

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

解法

令 $ f[i][j] $ 表示剩余区间为 $ [i,j] $ 时的最大得分差。

时间复杂度 $ \mathcal{O}(n^2) $

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 3001
ll f[N][N];
int a[N], n;
int main() {
    scanf("%d", &n);
    bool sign = n & 1 ? 1 : -1;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        f[i][i] = a[i] * sign;
    }
    for (int len = 1; len <= n; len++)
        for (int i = 1; i + len <= n; i++) {
            int j = i + len;
            f[i][j] = max(a[i] - f[i + 1][j], a[j] - f[i][j - 1]);
        }
    printf("%lld\n", f[1][n]);
    return 0;
}

M - Candies

题意

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

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

解法

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

时间复杂度 $ \mathcal{O}(n^2) $

代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 101
#define M 100001
int n, m;
int f[N][M], s[N][M];
int main() {
    scanf("%d%d", &n, &m);
    f[0][m] = s[0][m] = 1;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        for (int j = 1; j <= m; j++)
            f[i][j] = (s[i - 1][min(m, j + x)] - s[i - 1][j - 1] + mod) % mod;
        s[i][0] = f[i][0] = s[i - 1][x];
        for (int j = 1; j <= m; j++) s[i][j] = (s[i][j - 1] + f[i][j]) % mod;
    }
    printf("%d\n", f[n][0]);
    return 0;
}

N - Slimes

题意

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

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

解法

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

时间复杂度 $ \mathcal{O}(n^3) $

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 401
ll f[N][N], s[N][N];
int a[N], n;
int main() {
    memset(f, 0x3f, sizeof(f));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &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]);
        }
    }
    printf("%lld\n", f[1][n]);
    return 0;
}

O - Matching

题意

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

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

解法

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

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

时间复杂度 $ \mathcal{O}(2^n\times n) $

代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define N 22
int 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

题意

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

询问染色方案数。

解法

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

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

时间复杂度 $ \mathcal{O}(n) $

代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 100001
#define M 200001
int 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 $ 次幂的行列式。

使用矩阵快速幂即可，时间复杂度 $ \mathcal{O}(n^2 \log k) $

代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
ll 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 $ 的位数，时间复杂度 $ \mathcal{O}(md) $

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define N 10001
int 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 $ 的方案数。

时间复杂度 $ \mathcal{O}(n^2) $

代码

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 3002
int 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 $ 的兔子分好组的最大得分。

时间复杂度 $ \mathcal{O}(2^n\times n) $

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define M 65536
#define N 16
int 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 $ 个节点的树，将其每个节点染成黑色或白色，要求任意两个黑色节点之间的路径上无白色节点。

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

解法

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

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

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

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

时间复杂度 $ \mathcal{O}(n) $

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100001
vector<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] $ ，只需区间加值与维护全局最值的线段树即可。

时间复杂度 $ \mathcal{O}(n \log n) $

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200001
ll 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 $ 。

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

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

解法

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

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

$$s_i < \mathcal{W} + w_j$$ $$s_j \geq \mathcal{W} + w_i$$

化简得

$$s_i + w_i < s_j + w_j$$

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

问题化简为简单的背包，时间复杂度 $ \mathcal{O}(n(w+s+\log n)) $

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define M 20001
#define N 1001
struct 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) $ 。其中障碍格子无法达到。

询问太郎的移动方案数。

解法

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

时间复杂度 $ \mathcal{O}(n+m+k^2) $

代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 200001
int 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 $ 个石头的高度为 $ h_i $ 。现在要求小青蛙从 $ 1 $ 号石头跳到 $ n $ 号石头，每次小青蛙可以选择从 $ i $ 号石头跳到 $ i + s $ ( $ 1 \leq s \leq n - i $ )号石头，代价是起跳点与落点的高度差的平方加上一个常数 $ C $ 。询问你最小代价。

解法

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

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

时间复杂度 $ \mathcal{O}(n) $

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200001
ll 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题知识点涵盖广泛，题面描述清晰，题目质量很高，很值得入门选手尝试。