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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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 $ 且只包含 01 的字符串,使得得分尽可能大。询问你最大得分。

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

解法

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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 $ 在上。那么有

化简得

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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题知识点涵盖广泛,题面描述清晰,题目质量很高,很值得入门选手尝试。