dp入门30题
前言：本文章主要记录一些 \(dp\) 入门题，都是我做过的，希望读者能从这些基础题中打好 \(dp\) 扎实的基础，有不足的地方也欢迎指出。大部分是 \(CodeFoces\) 和 \(Atcoder\) 的题（可以公开代码）。
T1：
CF191A
题意：
给你若干字符串，\(a\) 可以拼接到 \(b\) 后面，当且仅当 \(b\) 的最后一个字符与 \(a\) 的第一个字符相同。
举个栗子：设 \(a,b\) 长度分别为 \(s1,s2\)，则拼接后新的字符串为 \(a+b\)，长度 \(s1+s2\)。
问这样拼出来得到的字符串第一个字母和最后一个字母相同的字符串的最大长度。
分析：
状态表示：\(dp(l,r)\) 表示以 \(l\) 开头，\(r\) 结束的字符串的最大长度。
不难看出，答案就是 \(\max\limits_{i=1}^{26}{dp(i,i)}\)
显然，转移只跟字符串长度，开头元素，末尾元素有关。
则可以写出状态转移方程：\(dp(j,s_{len})=max\{dp(j,s_1)+len\}\)
这里枚举转移的起点 \(j\)，\(s\) 是当前字符串，\(len\) 是串长。
时间复杂度 \(O(26n)\)，空间复杂度 \(O(26^2)\)
Code
T2:
CF455A
题意：
给你一个序列 \(a\)，每次可以选一个 \(x\)，把序列中 \(x-1\) 和 \(x+1\) 删除，贡献加 \(x\)，问贡献的最大值。
分析：
状态表示：\(dp_i\) 表示算了前 \(i\) 个数（指的是值域）。
正序枚举，然后这样就不需要考虑删除 \(i+1\) 了。
转移：\(dp_i=max\{dp_{i-2}+num_i \times i,dp_{i-1}\}\)
在删与不删中取最大值。
答案：\(dp_{max\{a_i\}}\)
不开 \(long\ long\) 见祖宗！。
Code
T3
CF1061C
题意：
给定一个序列 \(a\)，可以选出一个 \(a\) 的子序列 \(b\)，\(b\) 需要满足 $ \forall i|b_i $，问有多少个 \(b\) 满足条件。
分析：
状态表示：\(dp_{i,j}\) 表示 \(a\) 中前 \(i\) 个数，选了 \(j\) 个数的总方案数。
直接转移 \(dp_{i,j}+=dp_{i-1,j}\) （转移 \(1\) ）
当 \(a_i|j\)，则有转移 \(dp_{i,j}+=dp_{i-1,j-1}\) （转移 \(2\)）
总的来说就是：\(dp_{i,j}=dp_{i-1,j}+(a[i]\%j==0)\times dp_{i-1,j-1}\)
时间复杂度 \(O(n^2)\)。
然后就欢乐的 $ TLE $ 掉啦。
不难发现，前一维可以用滚动数组优化。
然后又不难发现，\(dp_{i,j}\) 是完全继承 \(dp_{i-1,j}\)，前面一维可以直接砍掉。
很容易发现，只有 \(j\) 是 \(a_i\) 的因子才会有转移 \(2\) 。
因此枚举 $ a_i $ 的因子，然后再转移，终于就开心的解决啦。
总的来说，就是 \(dp_{b_i}+=dp_{(b_i-1)}\)，\(b_i\) 表示 \(a_i\) 的第 \(i\) 个因子。
时间复杂度 $ O(n\sqrt n) $，空间复杂度 $ O(n) $。
Code
T4
luogu p2289
题意：
有 \(m\) 个任务，每个任务有起始时间，终止时间，和做完任务后得到的价值。做完一个任务后需要休息 \(r\) 的时间才能开始下一个任务，问在总时间 \(n\) 内能得到的最大价值。
分析：
状态表示：\(dp_i\) 表示前 \(i\) 段时间能够得到的最多牛奶。
状态转移：\(dp_i=max\{dp_i,dp_j+s\}\)
把挤奶时间按左端点最小排序，可以直接转移。
枚举第 \(j\) 段任务，看是否满足条件，然后转移。
答案：\(max\{dp_i\}\)
时间复杂度 \(O(m^2)\)，空间复杂度 \(O(m^2)\)。
Code
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e3+5;
struct pos
{
int l,r,s;
friend bool operator < (pos a,pos b)
{
return a.r<b.r;
}
}e[N];
int n,m,r,dp[N];
int main()
{
scanf("%d %d %d",&n,&m,&r);
for(int i=1;i<=m;i++) scanf("%d %d %d",&e[i].l,&e[i].r,&e[i].s);
sort(e+1,e+1+m);
e[0].r=-1e6;
for(int i=1;i<=m;i++)
for(int j=0;j<i;j++)
if(e[i].l-e[j].r>=r)
dp[i]=max(dp[i],dp[j]+e[i].s);
int ret=0;
for(int i=1;i<=m;i++) ret=max(ret,dp[i]);
printf("%d\n",ret);
return (0-0); // QwQ
}
T5
ABC265E
题意：
你最初在 \((0,0)\)，一共有三种操作，当你在 \((x,y)\)，你可以走到 \((x+a,y+b),(x+c,y+d),(x+e,y+f)\)，一共可以操作 \(n\) 次，有 \(m\) 个点不能走到，问操作 \(n\) 次后能够走的不同路径条数。（详细题目建议见原题，这里可能说的不太清楚）
分析：
容易发现，路径只与 \(3\) 种操作的操作次数有关，与先后无关，然后就可以 \(O(n^3)\) 搞了。
状态表示：\(dp_{i,j,k}\) 表示第一种操作 \(i\) 次，第二种 \(j\) 次，第三种 \(k\) 次能够走的路径条数。
状态转移：\(dp_{i+1,j,k}+=dp_{i,j,k},dp_{i,j+1,k}+=dp_{i,j,k},dp_{i,j,k+1}+=dp_{i,j,k}\)
答案：\(\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{n-i}\sum\limits_{k=0}^{n-i-j}dp_{i,j,k}\)
时间复杂度 \(O(n^3)\)，空间复杂度 \(O(n^3)\)。
Code
T6
CF414B
题意：
一个数列，后一个数能被前面整除，这个数列就叫做好数列，给定 \(n,k\)，请求出数列长度为 \(k\)，且数列最大值不超过 \(n\) 的好数列个数。
分析：
状态表示：\(dp_{i,j}\) 表示前 \(i\) 个元素中，第 \(i\) 个数为 \(j\) 的好数列个数。
状态转移：\(dp_{i,j}+=dp_{i-1,d}，j|d\)
答案：\(\sum\limits_{i=1}^{n}dp_{k,i}\)
时间复杂度 \(O(\sqrt{n}k^2)\)，空间复杂度 \(O(k^2)\)。
Code
T7
luogu p4310
题意：
给定长度为 \(n\) 数列 \(a\)，求 \(a\) 的子序列 \(b\)，满足 \(b_i\&b_{i-1}\neq 0,i\geq 2\)，求最长长度 \(b\) 的长度。
分析：
不难发现，\(dp_{i,j}\) 表示在数列 \(a\) 的前 \(i\) 个数中能够得到的最大长度。有的二进制位有，有的二进制位无，因此这就启发我们用二进制位作状态。
状态表示：\(dp_i\) 表示二进制位 \(i\) 存在时 \(b\) 的长度。
答案：\(\max\{dp_i\}\)
状态转移：\(dp_j=max\{dp_k+1\} (j\neq k)\)
时间复杂度 \(O(n)\)，空间复杂度 \(O(30)\)。
Code
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> PII;
typedef long long LL;
template <typename T> void inline read(T& x)
{
x=0; int f=1; char ch;
while((ch=getchar())>'9' || ch<'0') if(ch=='-') f=-1;
while(ch>='0' && ch<='9') x=x*10+(ch^'0'),ch=getchar();
x*=f;
}
int n,dp[35];
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
int x,k=1; read(x);
for(int j=0;j<=30;j++) if(x>>j&1) k=max(k,dp[j]+1);
for(int j=0;j<=30;j++) if(x>>j&1) dp[j]=max(dp[j],k);
}
printf("%d\n",*max_element(dp,dp+31));
return (0-0); // QwQ
}
T8
CF580D
题意：
有 \(n\) 种食物，可以依次选若干种食物，选第 \(i\) 种食物可以获得 \(a_i\) 价值，有 \(k\) 个条件，\(v_i\)在 \(u_i\) 后选可获得 \(w_i\) 价值，问共选 \(m\) 种后的最大价值。
分析：
状态设计：\(dp_{i,j}\) 表示选了状态为 \(i\) 的食物，当前最后一个选的是 \(j\)。
答案：\(\max\{dp_{i,j}\} (popcount(i)==m \&\& j \in i)\)
状态转移：\(dp_{i|(1<<k),k}=\max\{dp_{i,j}+a_k+b_{j,k}\}\ \ (k \notin i)\)
时间复杂度 \(O(n^22^n)\)，空间复杂度 \(O(n2^n)\)。
Code
T9
CF1110D
题意：
有 \(n\) 张牌，每张牌上有一个元素 \(a_i\) 在 \(1\) 到 \(m\) 范围内，每次可以取出三张牌，牌上元素连续或者相同，每张牌只能用一次，问最多能形成多少个三元组。
分析：
首先，可以肯定是，一定在值域 \(m\) 上做 \(dp\)。
设 \(dp_i\) 表示前 \(i\) 的数字能够得到的最多三元组数量。
然后发现不能统计 \(i\) 用了多少个，无法转移。
那就加一维 \(dp_{i,j}\) 表示前 \(i\) 个数字，\([i,i+1,i+2]\) 用了 \(j\) 个 \(i+2\) 得到的最多三元组数量。
这个可以由 \(i-1\) 那一维转移，但是这只能知道 \(i+2\) 的个数，不知道 \(i+1,i\)。
再加一维：\(dp_{i,j,k}\)表示前 \(i\) 个数字，\([i,i+1,i+2]\) 用了 \(j\) 个 \(i+2,k\) 个 \(i+1\)，的得到的最多三元组数量。
由于三个 \([i,i+1,i+2]\) 可以看成 \([i,i,i],[i+1,i+1,i+1],[i+2,i+2,i+2]\)。
那么 \(j,k\) 就是小于 \(3\) 的。
因此得到状态转移：\(dp_{i,j,k}=max\{dp_{i-1,k,l}+j+\frac{cnt[i]-j-k-l}{3}\}\)
枚举 \(j,k,l\)，表示 \(i+2,i+1,i\) 的个数。
答案：$\sum\limits_{j=0}{2}\sum\limits_{k=0}{2}dp_{m,j,k} $
时间复杂度 \(O(27m)\)，空间复杂度 \(O(9m)\)。
Code
特别感谢，wjr 大神的教导。
T10
CF2B
题意：
有一个 \(n\times n\) 的矩形，你需要找到一条路径，以左上角 \((1,1)\) 为起点，右下角 \(n,n\) 为终点的路径，使得经过的路径的点的数字的乘积末尾 \(0\) 个数最少。
每次只能向下或向右走，不能走出矩阵。
分析：
一些数要乘积末尾有 \(0\)，必须保证其中 \(2\) 和 \(5\) 的质因子都大于 \(0\)，因为 \(2\times 5=10\)。
因此第一问只需要求从起点到终点经过的质因子 \(2\) 和 \(5\) 的最少次数，答案取个 \(min\)。
对于第二问，基于第一问，从后向前倒推，找到这个状态转移的上一个状态，递归下去。
对于第一问的状态表示：\(dp_{i,j,0/1}\) 表示走到 \({i,j}\) 经过的质因子 \(2(0),5(1)\) 的最少次数。
状态转移：\(dp_{i,j,0/1}=min\{dp_{i-1,j,0/1},dp_{i,j-1,0/1}\}+s_{i,j,0/1}\)
注：此题矩阵中的元素非负，当有 \(0\) 时，走过的路径数字乘积经过 \(0\) 就变成 \(0\) 了，因此，当第一问答案不为 \(0\) 时，则方案就是从起点到 \(0\) 的位置，再到终点。
时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n^2)\)。
Code
T11
CF4D
题意：
给定序列 \(a,b\)，\(a,b\) 中每个元素有 \(w_i,h_i\)，求出 \(a,b\) 的最长二维上升子序列 \(c\)，保证 \(c\) 中，所有 \(h_i>h_{i-1},w_i>w_{i-1}\)，并且 \(c\) 中 \(w_i>w,h_i>h\)，输出 \(c\) 的长度和数组 \(c\)。
分析：
首先可以把 \(h_i\leq h\) 或 \(w_i\leq w\) 的舍去。
然后按 \(w_i\) 排序，然后跑一个裸的最长上升子序列。
状态表示：\(dp_i\) 表示以 \(i\) 结尾的最长上升子序列长度。
状态转移：\(dp_i=max\{dp_j+1\}\)，然后记录转移的路径。
第一问答案：\(max\{dp_i\}\)
第二问答案：最大的 \(dp_i\) 的下标 \(i\) 向前递推。
Code
T12
CF1096D
题意：
给定一个字符串 \(s\)，删除一个字符有代价，要求删除一些字符（\(0\) 个也行）使得 \(s\) 中不存在一个子序列为 \(hard\)。
分析：
题目要求子序列不能出现字符串 \(hard\)，不难发现，影响 \(hard\) 是否存在的是 \(har\) 后面是否有 \(d\) ,\(ha\) 后面是否有 \(rd\)，那这就很清楚了。
状态定义：\(dp_{i,j}\) 表示前 \(i\) 个字符中不存在长度为 \(j\) 的 \(hard\) 的前缀所需要的最小价值。
答案：\(min\{dp_{|s|,j}\},j\in (1,4)\) （我喜欢从 \(1\) 开始计数。）
状态转移：考虑一个字符 \(s_i\)，如果他为 \(hard\) 中的字符，那就找到他在 \(hard\) 中的下标，转移，反之直接继承。
具体点：\(dp_{i,j}=dp_{i-1,j-(s_i==”hard”_j)}\)
Code
T13
ABC267D
题意：
给定一个序列 \(a\)，需要求出 \(a\) 的一个长度为 \(m\) 子序列 \(b\)，使得 \(\sum\limits_{i=1}^{m}i\times b_i\) 最大。
分析：
可能会有一个错误的贪心，只选正数，这是不对的，比如 \(a=\{5,-1,6,1\},m=3\)，贪心会得出答案为 \(20\)（选 \(\{5,6,1\}\)），而实际为 \(21\)（选 \(\{5,-1,6\}\)）。
状态表示：\(dp_{i,j}\) 表示序列 \(a\) 的前 \(i\) 项中选了 \(m\) 个作为 \(b\) 的最答案。
答案：\(\max\{dp_{i,m}\}\)
状态转移：\(dp_{i,j}=max\{dp_{i-1,j-1}+a_i\times j,dp_{i-1,j}\}\)
分别表示将序列 \(a\) 的第 \(i\) 项作为 \(b\) 的第 \(j\) 项和不选。
比较裸，时间复杂度 \(O(nm)\)，空间复杂度 \(O(nm)\)。
Code
T14
ABC267G
题意：
给定序列长度为 \(n\) 的序列 \(a\)，需要求一个长度为 \(m\) 的子序列 \(b\)，使得 \(\sum\limits_{i=1}^{m}i\times b_i\) 最大。
分析：
一个很显然的状态设计：\(dp_{i,j}\) 表示前 \(i\) 个数中选了 \(j\) 个的最大价值。
答案：\(\max\limits_{i=1}^{n}dp_{i,m}\)
故有方程：\(dp_{i,j}=max\{dp_{i-1,j},dp_{i-1,j-1}+j\times a_i\}\)
Code
T15
CF1207C
题意：
城市里正在修轨道和支柱，分别花费 \(a,b\)。给定长度 \(n\) 的 \(01\) 序列，如果某一位为 \(1\) 表示这段轨道要通车，反之不需要，通车必须满足轨道高度大于等于 \(2\)。要保证所有通车高度为 \(2\) 的同时，修轨道和支柱花费最小。（更多细节请参见原题）。
分析：
贪心方面想，在通车阶段一定是要贡献 \(a+2b\)，这是毋庸置疑的，主要就是通车不通车交汇处，你要考虑他是保持高度为 \(2\) 还是降到 \(1\)。然后发现如果贪心，应该可以做，但是细节有点多，不好实现，因此考虑 \(dp\)。
状态表示：\(dp_{i,0/1}\) 表示第 \(i\) 段高度为 \(1(0),2(1)\) 时的最下花费。
答案： \(\min\{dp_{n,0}+b,dp_{n-1,1}+2\times (a+b)\}\)。 最后到终点高度为 \(1\)。
状态转移：\(\begin{cases}dp_{i,0}=min\{dp_{i-1,0}+a+b,dp_{i-1,1}+2\times (a+b)\}\\
dp_{i,1}=min\{dp_{i-1,0}+2\times a+b,dp_{i-1,1}+a+2\times b\}\end{cases}\)
对于通车段，只能从高度为 \(2\) 转移，而高度为 \(1\) 是做不到的，因此 \(dp_{i,0}\) 赋值正无穷，\(dp_{i,1}=dp_{i-1,1}+a+2\times b\)
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。
Code
T16
CF1625C
题意：
有两座城市 \(A,B\)，距离为 \(L\)，沿途有 \(n\) 个标识，第 \(i\) 个离 \(A\) 距离 \(d_i\)。表示从这里开始，速度不能超过 \(a_i\)。保证起点有标识，即 \(d_1=0\)。
现在可以移去其中至多 \(k\) 个标识，使 \(A\) 到 \(B\) 时间最短，输出时间。
分析：
这种题，看完第一想到的肯定是 \(dp\)，蛮经典的。
状态表示：\(dp_{i,j}\) 表示走到第 \(i\) 个标识，移去了其中 \(j\) 个的最短花费时间。
状态转移：\(dp_{i,j}=min\{dp_{i-o-1,j-o}+(d_i-d_{i-o-1})\times a_{i-o-1}\}\)
解释一下，很显然，枚举连续去掉了多少个标识(\(o\))，这样是显然并且正确的，转移看起来就很正确。
易错：最后一个标识位置可能不为 \(L\)，因此还需要多开一个点，保证一定能到终点。
答案：\(min\{dp_{n+1,i}\},i\leq k\)。
时间复杂度 \(O(nk^2)\)，空间复杂度 \(O(nk)\)。
Code
T17
CF1105C
题意：
你需要构造长度为 \(n\) 的序列，序列中的每一项值在 \([l,r]\) 中，要使序列元素总和为 \(3\) 的倍数，有多少种方案。
分析：
由于序列元素总和为 \(3\) 的倍数，那么只需要维护当前序列元素和模 \(3\) 的余数，有多少种即可。
因此可得状态表示：\(dp_{i,j}\) 表示当前序列长度为 \(i\)，序列元素和模 \(3\) 的余数为 \(j\)。
答案：\(dp_{n,0}\)
这里需要记录 \([l,r]\) 中，模 \(3\) 的余数为 \(0,1,2\) 的分别有多少，比较简单，两头判断，中间直接算即可。
状态转移：\(\begin{cases}dp_{i,0}=dp_{i-1,0}\times s_0+dp_{i-1,1}\times s_2+dp_{i-1,2}\times s_1\\dp_{i,1}=dp_{i-1,0}\times s_1+dp_{i-1,1}\times s_0+dp_{i-1,2}\times s_2\\dp_{i,2}=dp_{i-1,0}\times s_2+dp_{i-1,1}\times s_1+dp_{i-1,2}\times s_0\end{cases}\)
其实可以通过一些运算循环简化，但是这样写更易懂。
Code
T18
CF1743C
题意：
给定一个长度为 \(n\) 的序列 \(a\) 和字符串 \(s\)，对于字符串的第 \(i\) 位，如果 \(s_i\) 为 \(1\)，表示可以将答案贡献增加 \(a_{i-1}\) 或 \(a_i\)。问最大贡献。
分析：
此题可以贪心，但既然是 \(dp\) 专题，当然是介绍 \(dp\) 做法。
发现这个题只有两种状态，第 \(i\) 位是否有贡献。
因此有状态表示：\(dp_{i,0/1}\) 表示第 \(i\) 位选/不选的最大贡献。
状态转移：\(\begin{cases}dp_{i,0}=dp_{i-1,0}+a_{i-1},dp_{i,1}=max\{dp_{i-1,0},dp_{i-1,1}\}+a_i\ \ \ \ (s_i==1)\\dp_{i,0}=dp_{i,1}=max\{dp_{i-1,0},dp_{i-1,1}\}\ \ \ \ (s_i==0)\end{cases}\)
答案：\(min\{dp_{i,0},dp_{i,1}\}\)
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。
Code
T19
CF118D
题意：
给定一个 \(01\) 序列，请求出其中 \(0,1\) 的个数分别为 \(n0,n1\) 且最长的连续的 \(0\) 长度不超过 \(k1\)，最长的连续 \(1\) 的长度不超过 \(k2\) 的序列个数。
输出答案对 \(10^8\) 取模。
分析：
应该是比较显然的状态表示：\(dp_{i,j,k,0/1}\) 表示用了 \(i\) 个 \(0\),\(j\) 个 \(1\)，当前末尾 \(0/1\) 有 \(k\) 个连续。
答案：\(\sum\limits_{i=1}^{k0}dp_{n0,n1,i,0}+\sum\limits_{i=1}^{k1}dp_{n0,n1,i,1}\)
状态转移：\(\begin{cases}dp_{i,j,k,s}+=dp_{i-1,j,k-1,s}\\dp_{i,j,1,s}+=dp_{i-1,j,k,s\bigoplus 1}\end{cases}\)
\(s\) 表示当前末尾是 \(0/1\)，方程都是一样的，\(0/1\) 交换一下就行了，注意边界。
Code
T20
CF467C
题意：
给定一个长度为 \(n\) 的序列 \(a\)，需要求出他 \(m\) 个互不相交的长度为 \(k\) 的子串，权值最大，保证一定有解。
分析：
状态表示：\(dp_{i,j}\) 表示前 \(i\) 个数中，选出了 \(j\) 个子串的最大权值。
答案：\(dp_{n,m}\)
状态转移：\(dp_{i,j}=max\{dp_{i-1,j},dp_{i-m,j-1}+(s_i-s_{i-m}) (i \geq m)\}\)
Code
T21
CF706C
题意：
给定若干字符串，可以选择若干字符串，将他们翻转，花费为 \(a_i\)，问使得所有字符串不降序排序最小花费，不可能输出 \(-1\)。
分析：
不难发现，每个字符串是否需要翻转，只与上一个字符串有关，那么状态表示：\(dp_{i,0/1}\) 第 \(i\) 个字符串是否翻转。
记 \(s1\) 表示 \(s\) 翻转后的字符串。
状态转移：\(\begin{cases}dp_{i,0}=min\{dp_{i-1,0}\} \ \ \ \ s_i\geq s_{i-1}\\dp_{i,0}=min\{dp_{i-1,1}\} \ \ \ \ s_i\geq s1_{i-1}\\dp_{i,1}=min\{dp_{i-1,0}+a_i\} \ \ \ \ s1_i\geq s_{i-1}\\dp_{i,1}=min\{dp_{i-1,1}+a_i\} \ \ \ \ s1_i\geq s1_{i-1}\end{cases}\)
答案：\(min\{dp_{n,0},dp_{n,1}\}\)
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。
Code
T22
CF431C
题意：
有一棵满 \(k\) 叉树，树的每条边都有权值，每个非叶子节点指向 \(k\) 个儿子的边权分别为 \(1,2,3…k\)。请求出从根节点开始一直向下走到叶子节点，所经过的边权值和为 \(n\) 且其中至少一条边大于等于 \(d\) 的总方案数。
答案对 \(10^9+7\) 取模。
分析：
因为题目只要求至少一条边大于等于 \(d\)，因此直接设状态 \(dp_{i,j}\) 当前边权和 \(i\) 且当前边权值为 \(j\)，然后发现，有多条边权值和大于等于 \(d\) 会被重复统计。
因此转换状态表示：\(dp_{i,0/1}\) 表示当前边权和为 \(i\)，且当前是否存在边权大于等于 \(d\) 的点的方案数。
状态转移：\(\begin{cases}dp_{i,0}+=dp_{i-j,0}\ \ \ \ (j<d)\\dp_{i,1}+=dp_{i-j,0}\ \ \ \ (j\geq d)\\dp_{i,1}+=dp_{i-j,1}\end{cases}\)
答案：\(dp_{n,1}\)
Code
T23
CF607A
题意：
有 \(n\) 个激光塔排成一行，第 \(i\) 个的位置是 \(a_i\)(\(a_i\) 单调递增)，威力是 \(b_i\)。当第 \(i\) 个激光塔被激活，所有这个激光塔左边的与他举例小于等于 \(b_i\) 的激光塔会被摧毁，发出激光的激光塔不会被摧毁。现在从右向左一次开启没有被摧毁的激光塔。
你现在可以在第 \(n\) 个激光塔右边任意放置一个激光塔，问如何安排这个机关塔使得被摧毁的激光塔数量最少。
分析：
这题我想了好久，但还是摆了。
本题有个很显然的暴力，枚举最右边被摧毁的激光塔个数，再模拟一遍可以得出答案。
但复杂度是 \(O(n^2)\) 的，显然不能接受。
状态表示：\(dp_i\) 表示从位置 \(i\) 开始启动激光，能保留激光塔的最大个数，然后可以递推。
为了方便，我们记 \(v_i\) 表示位置 \(i\) 的激光威力值，\(v_i==0\) 表示此处没有激光塔。
方程：\(dp_i=\begin{cases}dp_{i-1}\ \ \ \ (v_i==0)\\dp_{i-v_i-1}+1\ \ \ \ (i-v_i-1 \geq 0)\\1\end{cases}\)
答案：\(n-\min\limits_{i=0}^{len}dp_i\)
Code
T24
CF1475G
题意：
给定 \(n\) 个数，选出若干个数，使得这若干个数中任意两个数，有一个是另一个的倍数，最大化选数个数（最小化删数个数）。
分析：
因为贪心无法维护，所以使用动态规划。
状态表示：\(dp_i\) 表示不超过 \(i\) 的数的最大选数个数，容易发现，转移只与他的倍数有关，然后就可以枚举他的倍数 \(j\)。
则有方程：\(dp_j=max\{dp_i,dp_j\}\)
答案就是 \(n-max\{dp_i\}\)。
\(dp_i\) 初始化为 \(cnt_i\) 表示 \(i\) 出现的次数。
Code
T25
CF1249E
题意：
给定 \(n,c\)，一栋楼有 \(n\) 层，上电梯（加等待时间）需要 \(c\)，走楼梯上一层楼时间 \(a_i\)，坐电梯上一层楼时间 \(b_i\)，问到达每一层楼最少需要的时间。
分析：
状态机模板。
状态表示：\(dp_{i,0/1}\) 表示在第 \(i\) 层，从 \(i-1\) 到 \(i\) 层是走楼梯 (\(0\)) 还是坐电梯 (\(1\)) 的最小时间。
状态转移：\(\begin{cases}dp_{i,0}=min\{dp_{i-1,0},dp_{i-1,1}\}+a_i\\dp_{i,1}=min\{dp_{i-1,0}+c,dp_{i-1,1}\}+b_i\end{cases}\)
初始化 \(dp_{1,1}=c+a_1\)
第 \(i\) 层答案 \(min\{dp_{i,0},dp_{i,1}\}\)
Code
T26
CFABC275E
题意：
给定 \(n,m,k\)，一个棋盘有 \(n+1\) 个格子，编号为 \(0,1…n\)，刚开始你在 \(0\)，然后可以投 \(k\) 次骰子，在 \([1,m]\) 中等概率的投到 \(s\)，走 \(s\) 步（如果当前位置编号大于 \(n\)），则多走的距离，你需要往回退（飞行棋都玩过吧）。求到终点 \(n\) 的期望。
答案对 \(998244353\) 取模。
分析：
考虑 \(n,m,k\) 都比较小，设 \(dp_{i,j}\) 表示投了 \(i\) 次骰子，当前在 \(j\) 的期望。
然后很容易发现，每次投骰子，每一面都有 \(\frac{1}{m}\) 的概率得到，分母就是 \(\frac{1}{m}\)。
设 \(pv\) 表示 \(m\) 在模 \(998244353\) 下的逆元。
枚举投的次数 \(i\)，上一次的位置 \(j\)，投到了数字 \(o\)，那么有转移。
\(\begin{cases} dp_{i,j+o}+=pv\cdot dp_{i-1,j}\ \ \ \ (j+o<n)\\dp_{i,n-(j+o-n)}+=pv\cdot dp_{i-1,j}\ \ \ (j+o>n)\end{cases}\)
初始化 \(dp_{0,0}=1\)
答案 \(\sum\limits_{i=1}^{k}dp_{i,n}\)
时间复杂度 \(O(nmk)\)，空间复杂度 \(O(nk)\)
Code
T27
CF1324E
题意：
一天有 \(h\) 小时，现在是 \(0\) 小时，你将会睡 \(n\) 次觉，每次可以选择睡 \(a_i\) 小时或 \(a_i-1\) 小时，当开始睡觉的那个小时 \(x\) 在 \([l,r]\) 中，那么这次睡眠是优秀的，求优秀睡眠次数最大次数。
分析：
每次睡觉有两种选择，当要睡觉时，并不知道当前睡觉时间，但却只与上次睡觉开始时间，时长有关，具有无后效行，考虑 \(dp\)。
状态表示：\(dp_{i,j}\) 表示第 \(i\) 次睡眠，开始睡觉的时间是 \(j\) 的优秀睡眠最大次数。
状态转移：\(dp_{i,j} = dp_{i-1,(j-a_i+h)\%h},dp_{i-1,(j-a_i-1+h)\%h}+(j\geq l\ \&\&\ j\leq r)\)
答案：\(\sum\limits_{i=0}^{h}dp_{n,i}\)
Code
T28
CF163A
题意：
给定字符串 \(a,b\)，求 \(a\) 的子串 \(x\)，\(b\) 的子序列 \(y\) 相等的个数。
答案对 \(10^9+7\) 取模。
分析：
直接设状态，感觉不好分析出状态，类比最长公共子序列。
状态表示：\(dp_{i,j}\) 表示 \(a\) 中以 \(i\) 结尾的子串，\(b\) 中以 \(j\) 结尾的子序列，满足题意的串个数。
转移方程：\(dp_{i,j} = dp_{i,j-1}+[a_i==b_j]\times (dp_{i-1,j-1}+1)\)
答案：\(\sum\limits_{i=1}^{n}dp_{i,|b|}\)
Code
T29
CF106C
题意：
有 \(n\) 克面团和 \(m\) 种不同馅料，第 \(i\) 种馅料有 \(a_i\) 克，做一个第 \(i\) 种面包，需要 \(b_i\) 克第 \(i\) 种馅料，\(c_i\) 克面团，这种面包一个卖 \(d_i\)。
当做没有馅料的面包，需要 \(c_0\) 克面团，可卖 \(d_0\)。
现在你需要求出在面团和馅料都够的情况下。能改卖的最大价值。
分析:
此题应该用背包解决。
状态表示：\(dp_{i,j}\) 表示用前 \(i\) 种馅料做面包，用了 \(j\) 克面团能够获得的最大价值。
答案：\(\max\limits_{i=0}^{n}dp_{m,i}+\left\lfloor\frac{(n-i)}{c_0}\right\rfloor\times d_0\)
分别枚举 \(i,j,k\) 表示第 \(i\) 种馅饼，当前用了 \(j\) 克面团，第 \(i\) 种馅饼用了 \(k\) 个。
状态转移：\(dp_{i,j}=max\{dp_{i-1,j-c_i\times k}+d_i\times k\}\)
Code
T30
CF1051D
题意：
有一个 \(2\times n\) 的网格，要在网格中填入黑块和白块，使得网格中恰好有 \(m\) 个连通块，求方案数。
答案对 \(998244353\) 取模
分析：
考虑到这是个 \(2\times n\) 的网格，填入的块状态有限，可以直接把每一列的块写入状态。
因此有方程 \(dp_{i,j,k} (k \in [0,3])\) 表示前 \(i\) 列中，共有 \(j\) 个连通块，第 \(i\) 列的状态是 \(k\)。
答案：\(\sum\limits_{i=0}^{3}dp_{n,m,i}\)
我这里设块的状态为：
\(0\ \ 1\ \ \ 2\ \ 3\)
\(W W B B\)
\(W B W B\)
转移也比较明显：
\(\begin{cases}dp_{i,j,0}=dp_{i-1,j,0}+dp_{i-1,j,1}+dp_{i-1,j,2}+dp_{i-1,j-1,3}\\dp_{i,j,1}=dp_{i-1,j-1,0}+dp_{i-1,j,1}+dp_{i-1,j-2,2}+dp_{i-1,j-1,3}\\dp_{i,j,2}=dp_{i-1,j-1,0}+dp_{i-1,j-2,1}+dp_{i-1,j,2}+dp_{i-1,j-1,3}\\dp_{i,j,3}=dp_{i-1,j-1,0}+dp_{i-1,j,1}+dp_{i-1,j,2}+dp_{i-1,j,3}\end{cases}\)
