给出 $n$ 个工人和 $m$ 件装备，装备的编号为 $1, 2, 3 … m$。
对于工人 $i$ ，他有三个参数 $a_i, b_i, c_i$，当为这个工人装备了第 $j$ 个装备时，需要花费 $a_i j ^ 2+ b_i j + c_i$ 的费用。
当为 $k$ 个工人装备上装备时，最小花费是多少。
对所有的 $k$ 的情况均需要输出
费用流
将每个员工与源点链接，取每个员工的二次函数曲线的最小值附近的 $n$ 个点，与员工相连，所有的在二次函数曲线上的点与汇点相连，员工连接到二次函数的线需要设定费用，其他线费用均为 $0$，所有线的流量均为 $1$
输出每次 spfa 过程中得到的费用即可
1 | |
有一串字符串，仅由 ${0, 1, 2, 3}$ 组成，长度为 $n$，同时满足 $m$ 个条件。每个条件由三个整数组成：$l、r、x$ 表示在这个字符串的 $[l, r]$ 这个区间内，有且仅有 $x$ 个不同的字符，求问可能的组合有多少种（mod 998244353）
因为前几天刚刚写了牛客暑期多校第二场，其中有一道题：ABBA（我的题解）感觉有点接近，所以第一想法就是dp了。但是这道题的字符多，不能像ABBA一样压缩至一维。所以只能想想看当时牛客官方给的题解的方法了。
考虑到之后需要判断条件是否满足，所以我第一感觉就是得定义一个超多维度的dp数组：1
2const int MAXN = 110;
long long dp[MAXN][MAXN][MAXN][MAXN][MAXN];
各个维度的定义如下：
对于 dp[a][b][c][d][t]
表示整个字符串长度为 t ，最后一次出现 0 的位置为 a，最后一次出现 1 的位置为 b ，最后一次出现 2 的位置为 c ，最后一次出现 3 的位置为d
然后可以得到状态转移方程1
2
3
4dp[t + 1][b][c][d][t + 1] += dp[a][b][c][d][t];
dp[a][t + 1][c][d][t + 1] += dp[a][b][c][d][t];
dp[a][b][t + 1][d][t + 1] += dp[a][b][c][d][t];
dp[a][b][c][t + 1][t + 1] += dp[a][b][c][d][t];
当然这个数组肯定是没法开的，所以把 t 压缩了，变成滚动dp1
2const int MAXN = 110;
long long dp[MAXN][MAXN][MAXN][MAXN][2];
然后通过滚动的方式来实现。
但是这并不是卡死这种方法的原因。
根据上面这些，可以写出整个dp过程，大概就是这样：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16for (int t = 1; t <= n; t++) {
for (int a = 0; a <= t; a++)
for (int b = 0; b <= t; b++)
for (int c = 0; c <= t; c++)
for (int d = 0; d <= t; d++)
dp[a][b][c][d][t & 1] = 0;
for (int a = 0; a <= t; a++)
for (int b = 0; b <= t; b++)
for (int c = 0; c <= t; c++)
for (int d = 0; d <= t; d++) {
dp[t + 1][b][c][d][t & 1] += dp[a][b][c][d][t ^ 1];
dp[a][t + 1][c][d][t & 1] += dp[a][b][c][d][t ^ 1];
dp[a][b][t + 1][d][t & 1] += dp[a][b][c][d][t ^ 1];
dp[a][b][c][t + 1][t & 1] += dp[a][b][c][d][t ^ 1];
}
}
这个复杂的……这还没加上判断是否满足条件……
无论是时间是还是空间上，估计都悬（时间上应该是一定过不了了）
然后只能继续压缩。
考虑到最后无论哪种状态下，$a, b, c, d$ 四个变量中，必定有一个且仅有一个变量的值为 t 。而且在这道题中，字符 ${0, 1, 2, 3}$ 完全等价。所以我们再压缩一维1
2const int MAXN = 110;
long long dp[MAXN][MAXN][MAXN][2];
此时的意义如下：
对于变量 dp[x][y][z]
表示字符 ${0, 1, 2, 3}$ 中，其中一个最后出现的位置为当前的字符最后（由于这个条件恒成立，所以并未被记录在数组中），剩下的三个字符分别出现在$x, y, z$处，且保证 $i < x \leq y \leq z (i 为当前字符长度)$ （仅当 $x = y = 0$ 时满足前面一个等于号，后面的等于号同理。而字符串长度至少为1，且此时$x、y、z$均为0，所以不存在 $i = x$ 的情况。）而后面的长度为 2 的维度指代当前状态和 上一个状态（滚动dp）
可以得到状态转移方程：1
2
3
4
5// i 为当前字符串长度，cur 为当前状态，last 为上一个状态
dp[x][y][z][cur] += dp[x][y][z][last];// 加入的字符与上一个加入的字符相同
dp[i - 1][y][z][cur] += dp[x][y][z][last];
dp[i - 1][x][z][cur] += dp[x][y][z][last];
dp[i - 1][x][y][cur] += dp[x][y][z][last];
得到整个 dp 过程：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22dp[0][0][0][0] = 1;
int cur = 1;
int last = 0;
for (int i = 1; i <= n; i++)
for (int x = 0; x <= i; x++)
for (int y = 0; y <= x; y++)
for (int z = 0; z <= y; z++)
dp[x][y][z][cur] = 0;
for (int x = 0; x < i; x++)
for (int y = 0; y <= x; y++)
for (int z = 0; z <= y; z++) {
dp[x][y][z][cur] += dp[x][y][z][last];
dp[i - 1][y][z][cur] += dp[x][y][z][last];
dp[i - 1][x][z][cur] += dp[x][y][z][last];
dp[i - 1][x][y][cur] += dp[x][y][z][last];
dp[x][y][z][cur] %= mod; // 别忘了 mod
dp[i - 1][y][z][cur] %= mod;
dp[i - 1][x][z][cur] %= mod;
dp[i - 1][x][y][cur] %= mod;
}
swap(cur, last);
考虑条件
需要判断一个区间内是否满足有多个不同的字符
我们可以根据区间右端为基准，当前dp的字符串长度到达一个条件的右端的时候，通过 $x、y、z$ 的值来判断是否到达了要求，如果没有则将此 dp 的赋值为0。如果懒得思考可以直接分类讨论一下就行了。虽然代码会比较长。
1 | |
把“时间粒子”作为最大流的计算结果
设置超级源点为 0
顾客点范围为 1 - 204
时间点 205 - 610
超级汇点 615
超级源点与所有顾客连线，容量为需求的烤肉数 * 需求的每块烤肉的时间（即此顾客需要占用的总时间粒子）
顾客与时间点进行连线，仅当此时间点在顾客等待的时间段内，容量为INF
每个时间点与汇点连线，容量为 m
1 | |
