Luogu P1192 台阶问题 Link
简要题意：给定台阶数 \(n\le1e5\) 和一步至多跨越台阶数 \(k\le1e2\) ，初始在 \(0\) 级，求方案数 \(\pmod {1e5+3}\)。
思路：设 \(f_i\) 表示走到第 \(i\) 级台阶的方案数，题意直接说明了可以从前 \(k\) 级台阶转移过来，考虑每次在以经处理好的台阶前新加一级产生的影响就是对于之后的 \(k\) 级的每一种方案都新产生了一种方案。所以有转移方程：
\[f_i=\sum_{j=i-k}^{i-1}f_j \]最后答案就是 \(f_n\)。
暴力转移即可通过，复杂度 \(O(kn)\)。
也可以对 \(f\) 前缀和优化成 \(O(n)\) 。
$O(n)$ 前缀和优化代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, mo = 1e5 + 3;
int f[maxn], s[maxn], n, k;
int main() {
ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
f[1] = 1, s[1] = 1;
for(int i = 2; i <= n + 1; i++) {
f[i] = (s[i - 1] - s[max(0, i - k - 1)] + mo) % mo;
s[i] = (s[i - 1] + f[i]) % mo;
}
cout << f[n + 1];
}
Luogu P1091 合唱队形 Link
简要题意：给出 \(n\le1e2\) 和 \(n\) 个有序身高 \(t_i\)，求出最小的 \(k\) 使得除去 \(k\) 个人剩下 \(n-k\) 个身高形成先严格单增再严格单减的序列。
思路：无论是从起始点还是终止点开始考虑都很困难，再加上枚举中间点朴素转移可以达到 \(O(n^5)\) 的时间复杂度。这是不能接受的。考虑若分别求出从一点结尾的最长上升子序列和从一点开始的最长下降子序列，把两段拼起来 \(-1\) 就能得到所有中间点构成的符合题意的序列长度。其中的最大值即 \(n-k\) 的最大值，这样就求出了最小的 \(k\) 。
求最长上升子序列和下降子序列可以做到 \(O(n\log n)\)，当然朴素的 \(O(n^2)\) 也能通过。
$O(n^2)$ 朴素dp代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 5;
int n, h[maxn];
int f1[maxn], f2[maxn];
int main() {
ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = 1; i <= n; i++){
f1[i] = 1;
for(int j = 1; j < i; j++) {
if(h[j] < h[i]) f1[i] = max(f1[i], f1[j] + 1);
}
}
for(int i = n; i >= 1; i--){
f2[i] = 1;
for(int j = i + 1; j <= n; j++) {
if(h[j] < h[i]) f2[i] = max(f2[i], f2[j] + 1);
}
}
int res = 0;
for(int i = 1; i <= n; i++) res = max(res, f1[i] + f2[i] - 1);
cout << n - res;
}
Luogu P1280 尼克的任务 Link
简要题意：有 \(k\le1e4\) 个任务，分布在时间 \(n\le1e4\) 中，给出每个任务的起始时间 \(l\) 和持续时长 \(t\) (左开右闭)，要求从 \(t=1\) 开始有任务起始时必须选择一个任务做，求最长空闲时间。
思路：考虑把最长休息时间作为状态，如果正序枚举，发现选择做任务会对之后未赋值的状态产生影响，有后效性。所以倒序转移。设 \(f_i\) 表示时间 \(i\) 开始做任务的最长休息时间。如果这个时间 \(i\) 没有起始的任务，即这个时间是空闲的，那么直接由时间 \(i+1\) 转移过来；如果有起始的任务，那就在这些任务完成时间中休息时间最长的作为转移。所以有转移方程：
\[f_i=\begin{cases} \max \limits_{l_j=i}f_{i+t_j} & \exists l_j=i\\ f_{i+1}+1 & Otherwise. \end{cases} \]最后答案是 \(f_1\) 。
倒序枚举状态，枚举所有任务找起始时间 \(l_j=i\) 的 \(j\) 转移，复杂度 \(O(kn)\)。
实际上可以用桶排序优化找的那一步，复杂度优化到 \(O(n+k)\)。
$O(kn)$ dp代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
int n, k;
int l[maxn], t[maxn];
int f[maxn];
int main() {
ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= k; i++) cin >> l[i] >> t[i];
for(int i = n; i >= 1; i--) {
bool flag = false;
for(int j = 1; j <= k; j++) {
if(i == l[j]) {
flag = true;
f[i] = max(f[i], f[i + t[j]]);
}
}
if(!flag) f[i] = f[i + 1] + 1;
}
cout << f[1];
}
这个题也可以转换成图论最短(长?)路，这里不多提。
Luogu P5664 Emiya 家今天的饭 Link
简要题意： 给定 \(n\le1e2, m\le2e3\) 的 \(n\times m\) 矩阵，横行纵列分别表示不同的烹饪方法和主要食材，矩阵上每个数表示会做的不同主菜。对于不同的做菜方案有以下限制：1.每个方案至少有一道菜；2.每个烹饪方法互不相同；3.每个菜品数量为 \(k\) 的方案每种主要食材不超过 \(\lfloor\frac k2\rfloor\) 个。求方案数 \(\bmod{998244353}\) 。
思路：先理解题意，菜品数 \(k\) 应该不超过 \(n\) 且不小于 \(2\) 。对于每个格子的菜，选择了那么同一行的其它菜就不能选了，所以转移时同一行的菜属于同一个过程，根据加法原理可以加起来作为一个整体记为 \(sum_i\) 。发现第三个限制很棘手，菜的数量要分开考虑，每一列的状态也要分开考虑，这样的时间和空间是难以接受的。
考虑容斥，拿所有的方案数减去不合法的方案数。
满足限制一二的所有方案：对于每一行的菜品，包括不取一共有 \(sum_i+1\) 种情况，根据乘法原理有 \(\prod_{i=1}^n(sum_i+1)-1\)，其中减去的 \(1\) 的是每一行都不取的情况(第一条限制)。
不合法方案：由于要违反第三限制，我们需要某些列选择的菜品数大于 \(\lfloor\frac k2\rfloor\)。然而这样的列如果存在那么有且仅会只有这一列，因为其它列的菜品数之和小于 \(\lfloor\frac k2\rfloor\)。不妨枚举单独的一列 \(t\) 选择的菜品数为 \(k'\)；为了转移的方便，我们考虑前 \(i\) 行其他列选 \(j\) 个。那么我考虑对于 \(f_{i,j,k'}\) 的转移方程：首先，对于在 \(i\) 行中选一种菜，如果选第 \(t\) 列，产生的方案数为 \(f_{i-1,j,k'-1}\times a_{i,t}\)；接着，对于不选 \(t\) 列的情况，产生的方案数为 \(f_{i-1,j-1,k'}\times (sum_i-a_{i,t})\)；最后，如果不在第 \(i\) 行选菜，继承先前的方案数 \(f_{i-1,j,k'}\)。即有转移方程：
实现时要枚举 \(t,i,j,k'\)，最后在总方案数中把 \(k'>j\) 的 \(f_{i,j,k'}\) 减掉就是合法的方案数。
复杂度达到 \(O(mn^3)\)。这对于大部分测试点来说足够，但是无法通过全部数据。
优化：考虑到 \(j,k'\) 是我们为了找到不合法方案数的指标，实际上只与它们的相对大小有关，而与其具体的值无关。不妨令 \(j'=k'-j\)，再将值域整体向右平移 \(n\) 处理掉负指标。一一对应上文的三种情况，产生方案数分别有 \(f_{i-1,j'-1}\times a_{i,t}\)、\(f_{i-1,j'+1}\times (sum_i - a_{i,t})\)、\(f_{i-1,j'}\)。即有新的转移方程：
\[f_{i,j'}=f_{i-1,j'-1}\times a_{i,t}+f_{i-1,j'+1}\times (sum_i - a_{i,t})+f_{i-1,j'} \]现在实现时只需要枚举 \(t,i,j'\) 三个指标，总方案数减去 \(1\le j'\le n\) 的 \(f_{i,j'+n}\) 即为答案。
复杂度 \(O(mn^2)\)。可以通过所有数据。
$O(mn^2)$ 优化后代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 10, maxm = 2e3 + 10, mo = 998244353;
int n, m, a[maxn][maxm];
ll s = 1, sum[maxn], f[maxn][maxn << 1];
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 >> a[i][j];
(sum[i] += a[i][j]) %= mo;
}
s = 1ll * s * (sum[i] + 1) % mo;
}
(s += mo - 1) %= mo;
for(int t = 1; t <= m; t++) {
f[0][n] = 1;
for(int i = 1; i <= n; i++) {
for(int j = n - i; j <= n + i; j++) {
f[i][j] = f[i - 1][j];
(f[i][j] += 1ll * f[i - 1][j - 1] * a[i][t] % mo) %= mo;
(f[i][j] += 1ll * f[i - 1][j + 1] * (sum[i] - a[i][t]) % mo) %= mo;
}
}
for(int j = 1; j <= n; j++) {
(s += mo - f[n][j + n]) %= mo;
}
memset(f, 0, sizeof f);
}
cout << s;
}