描述 给定一个区间[a,b][a,b][a,b]，为在这个区间当中[0,9]每个数字出现在各个数位上的次数 思路 数位dp模板题目，设dp[i][j][k]dp[i][j][k]dp[i][j][k]表示考虑到第iii位，要计算的数是jjj，并且jjj之前出现了kkk次的方案数，采用记忆化搜索的方式进行dp 采用dfs进行数位dp，具体的转移方法比较晦涩，可以参考代码注释 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll f[15][10][15]; int num[15]; ll...

描述 给定两个字符串a和b，将两个字符串合并为c，要求两个字符串内部的顺序不变，求c的最长回文子串最大为多大 思路 区间dp的入门题目，设dp[la][ra][lb][rb]dp[la][ra][lb][rb]dp[la][ra][lb][rb]表示考虑字符串a的[la,ra)[la,ra)[la,ra)和字符串b的[lb,rb)[lb,rb)[lb,rb)，能否组成一个回文字符串，则转移方程为 dp[la][ra][lb][rb]={truedp[la+1][ra−1][lb][rb]==true and a[la]==a[ra]truedp[la+1][ra][lb...

描述 给一个长度为nnn的空字符串，每次选定一个子串染色，问将字符串染成目标颜色的最小次数 思路 经典的区间dp的题目，设dp[i][j]dp[i][j]dp[i][j]表示将区间[i,j][i,j][i,j]染成目标颜色的最小花费，转移方程为 dp[i][j]={mink∈[i,j](dp[i][k]+dp[k][j])min(dp[i+1][j],dp[i][j−1])当s[i]==s[j]时才考虑这种情况dp[i][j]=\begin{cases}min_{k \in [i,j]}(dp[i][k]+dp[k][j]) \\min(dp[i+1][j],dp[i][j-1]) &am...

描述 给一个数组，要求从数组中选取一些数，使得这些数的和为kkk的倍数且和最大 思路 类似于背包的一个题，设dp[n][m]dp[n][m]dp[n][m]表示考虑前nnn个数，选取的数对kkk取模为mmm的最大价值 转移方程为dp[n][m]=dp[n−1][(m−a[n])%k]+a[n]dp[n][m]=dp[n-1][(m-a[n])\%k]+a[n]dp[n][m]=dp[n−1][(m−a[n])%k]+a[n] 采用滚动数组节省内存 代码 #include<bits/stdc++.h> using namespace std; typedef long long ...

描述 在一棵树上选择一些点，要求选择的点不相邻，问最多选多少点 思路 设dp[i][0]dp[i][0]dp[i][0]表示以iii为根的子树且不选iii节点最多能选多少点，dp[i][1]dp[i][1]dp[i][1]表示以iii为根的子树且选iii节点最多能选多少点，令树的根为sss，由于sss节点必须选，则答案为dp[s][1]dp[s][1]dp[s][1] 转移方程为{dp[i][1]=∑v是i的儿子dp[v][0]dp[i][0]=∑v是i的儿子max(dp[v][0],dp[v][1])\begin{cases}dp[i][1]=\sum_{v是i的儿子}dp[v][0]\\...

描述 问有多少字符串满足以下条件： 长度不超过nnn 包含子序列us 结果对1e9+71e9+71e9+7取模 思路 典型的dp问题，设dp[n][0]dp[n][0]dp[n][0]表示长度为nnn且不包含字母u的字符串数目，dp[n][1]dp[n][1]dp[n][1]表示长度为nnn字母u的字符串数目，dp[n][2]dp[n][2]dp[n][2]表示长度为nnn且包含子序列us的数目，答案为∑i≤ndp[i][2]\sum_{i \leq n}dp[i][2]∑i≤n​dp[i][2] 转移方程为{dp[n][2]=dp[n−1][1]+26∗dp[n−1][2]dp[n][...

描述 给一个n∗mn*mn∗m的字母矩阵，每个字母对应一个价值，问从左上角出发所能达到的最大价值 思路 二维DP，令dp[i][j]dp[i][j]dp[i][j]表示从左上角到达(i,j)(i,j)(i,j)所能得到的最大价值，则答案为dp[n][m]dp[n][m]dp[n][m]，初始化时，所有dp[i][j]dp[i][j]dp[i][j]的值为当前点的价值，转移方程为dp[i][j]=max⁡(dp[i−1][j]+dp[i][j],dp[i][j−1]+dp[i][j])dp[i][j]=\max(dp[i-1][j]+dp[i][j],dp[i][j-1]+dp[i][j])d...

描述 给一个长度为nnn的数组aaa，mmm次操作，左上角为(x1,y1)(x_1,y_1)(x1​,y1​)，右下角为(x2,y2)(x_2,y_2)(x2​,y2​)加kkk，问mmm次操作后的数组 思路 差分模板题，由于仅有一次查询，因此可以利用前缀和的性质，设数组sumsumsum表示mmm次操作后，每个位置增加的数为多少，则每次操作将sum[x1][y1]+ksum[x_1][y_1]+ksum[x1​][y1​]+k，sum[x2+1][y1]−ksum[x_2+1][y_1]-ksum[x2​+1][y1​]−k,sum[x1][y2+1]−ksum[x_1][y_2+1]-k...

描述 给一个长度为nnn的数组aaa，mmm次操作，每次将区间[l,r][l,r][l,r]加kkk，问mmm次操作后的数组 思路 差分模板题，由于仅有一次查询，因此可以利用前缀和的性质，设数组sumsumsum表示mmm次操作后，每个位置增加的数为多少，则每次操作将sum[l]+ksum[l]+ksum[l]+k，sum[r+1]−ksum[r+1]-ksum[r+1]−k，最后对数组sumsumsum求前缀和 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAX...

描述 给一棵根为111的树，树上部分节点被染色，qqq次询问，每次询问某个节点的子树中有多少被染色的结点 思路 树形DP模板题，设dp[i]dp[i]dp[i]为节点iii为根的子树有多少节点被染色，初始化时，如果节点iii被染色，则dp[i]=1dp[i]=1dp[i]=1否则为000 转移方程为 dp[i]=dp[i]+∑j是i的儿子dp[j]dp[i]=dp[i]+\sum_{j是i的儿子}dp[j]dp[i]=dp[i]+∑j是i的儿子​dp[j] 代码 #include<bits/stdc++.h> using namespace std; const int MAX...

描述 有一个体积为VVV的背包，nnn个物体，每个物体的体积和价值分别为viv_ivi​和wiw_iwi​，每个物品仅可用多次，问: 背包能装的最大价值是多少？ 将背包装满后的最大价值是多少？ 思路 完全背包的模板题，第一问答案为maxi≤Vdp[i]max_{i \leq V}dp[i]maxi≤V​dp[i]，第二问答案为dp[V]dp[V]dp[V] 设dp[i][j]dp[i][j]dp[i][j]表示使用了iii个物体体积为jjj时的最大价值，01背包的转移方程为dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]+w[i])dp[i][j]=max(d...

描述 有一个体积为VVV的背包，nnn个物体，每个物体的体积和价值分别为viv_ivi​和wiw_iwi​，每个物品仅可用一次，问: 背包能装的最大价值是多少？ 将背包装满后的最大价值是多少？ 思路 01背包的模板题，第一问答案为maxi≤Vdp[i]max_{i \leq V}dp[i]maxi≤V​dp[i]，第二问答案为dp[V]dp[V]dp[V] 设dp[i][j]dp[i][j]dp[i][j]表示使用了iii个物体体积为jjj时的最大价值，01背包的转移方程为dp[i][j]=max(dp[i−1][j],dp[i−1][j−v[i]+w[i])dp[i][j]=max(d...

描述 给定一个不超过1e181e181e18的整数，选择101010进制下部分数位的数，使得选择数的和等于没选数的和 思路 反正只有181818位，直接枚举选择哪些数位暴力就好了，最坏复杂度O(218)O(2^{18})O(218)貌似不用DPDPDP啊 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; int nums[20]; int main() { ll x; int len=0,sum=0; scanf("%lld",&x); for(i...

描述 给定一个n∗mn*mn∗m的矩阵，qqq次询问，每次询问(x1,y1)(x_1,y_1)(x1​,y1​)为左上角，(x2,y2)(x_2,y_2)(x2​,y2​)为右下角的子矩阵的和 思路 二维前缀和的模板题，设矩阵aaa中，左上角为(1,1)(1,1)(1,1)，右下角为(x,y)(x,y)(x,y)的矩阵和为sum[x][y]sum[x][y]sum[x][y]，根据容斥原理转移公式为sum[x][y]=sum[x−1][y]+sum[x][y−1]−sum[x−1][y−1]+a[x][y]sum[x][y]=sum[x-1][y]+sum[x][y-1]-sum[x-1]...