本文篇幅有点长了...由于这两道题目有点难想要说清楚确实需要很大量的文字逻辑推理因为这两题我个人觉得比较相近所以放到一起了大家可以根据目录自行选择想看的部分看。在常规的动态规划 DP 题目中比如背包 DP 我们通常都是习惯于以 dp[i][j] 两个维度表示当前的“位置”和“代价”。但如果题目有其他的限制比如在大区间内选择出最优的k 个小区间等等这时我们就不得不在 dp 数组多开几个维度而且还要将各种状态塞入 dp 数组维度里来保证我们计算的逻辑严密性。这两道题目都是涉及 K 个区域的划分还有需要我们对于 dp 的状态理解更深入的题目两题各有相似之处看完也能更好提升做 DP 题目的思路。洛谷P2679题目链接P2679 [NOIP 2015 提高组] 子串 - 洛谷洛谷的 P2679 就是一道比较典型的题目。说实话第一次碰到这种题我就算能看出这用的是动态规划 DP 也很难一下想到要怎么个思路去表示这个 dp 数组。但我们只要冷静仔细分析就能很好看出它的做法了。首先暴力肯定走不通的所以我们首选当然是 DP 。那我们既然要在字符串 A 里选出一些子串组合与字符串 B 相等。所以很显然我们的 dp 数组必然有 dp[i][j] 两个状态了。表示在字符串 A 的前 i 个字符里选出几个子串组合起来与字符串 B 里前 j 个字符相等的方案数。但这当然远远不够我们做动态规划 DP 题目必须要敢于开多维的数组。不能说一直想着开三维四维的数组会不会出问题会不会 MLE 什么的。数组大了我们后续可以优化但我们想要做出题目 dp 数组里每一维都代表一种状态丢失一种状态我们的状态转移就不够严密那就推导不出结果了。所以也很显然我们还需要记录下我们当前已经划分出来几个子串了。所以我们的dp[i][j][k] 应该表示在字符串 A 的前 i 个字符里选出 k 个子串组合起来与字符串 B 里前 j 个字符相等的方案数。到这里似乎就状态选得差不多了。但是还是不够我们推导到了字符串 A 的第 i 个字符的时候我们会有个疑问这个第 i 个字符我们到底选没选而且可以发现当前这个字符选不选和上一个字符选没选也同样有很强烈的关系如果这个字符我选了上一个字符没选那就是说明当前这个字符属于的是一个全新的子串如果这个字符我选了上一个字符也选了那不就说明了这两个字符同属于一个子串里吗......所以最后经过我们的分析当前这个字符 i 选没选同样很重要既然我们的推导离不开这个字符 i 选不选的状态我们就还要新开一个状态来记录当前字符 i 我们到底选没选。所以最终的 dp 数组状态定义就如下1. dp[i][j][k][0] 在字符串 A 的前 i 个字符里选出 k 个子串且当前字符 i 没有被选择入子串表现为0组合起来与字符串 B 里前 j 个字符相等的方案数。2. dp[i][j][k][1] 在字符串 A 的前 i 个字符里选出 k 个子串且当前字符 i 被选择入子串表现为1组合起来与字符串 B 里前 j 个字符相等的方案数。虽然状态看起来很复杂但是我们刚刚经过分析实际上每一个状态都是不可或缺的。现在状态充足了我们就可以推导一下状态转移方程了。此时其实还有一件很重要的事情字符串 A 和字符串 B在处理到各自的 i 和 j 个字符的时候i 字符和 j 字符是否相同呢这个同样重要我们需要严密的分类讨论一下。情况一A[i] ! B[j]先来讨论一下 i 字符和 j 字符不同的情况。首先是 dp[i][j][k][0] 根据我们的定义既然当前这个字符 i 我们都没选了那上一个字符其实选和不选都可以了而且所有选择的子串都在前面。而且既然我们都不选第 i 个字符了所以也不用管第 i 个字符和第 j 个字符什么关系了。所以在字符串 A 前面 i-1 个字符里我们选出了 k 个子串组合和字符串 B 前 j 个字符串相同。所以很好推出dp[i][j][k][0]dp[i-1][j][k][0]dp[i-1][j][k][1]而 dp[i][j][k][1] 根据定义我们选择了第 i 个字符作为子串部分可是第 i 个字符甚至都不和字符串 B 的第 j 个字符相等所以答案很明显这个状态是不合理的选择了第 i 个字符这个字符串 A 的结尾部分作为子串部分了而它不和字符串 B 的结尾部分第 j 个字符相等这是不合理的。所以直接得出dp[i][j][k][1]0情况二A[i] B[j]此时 i 字符和 j 字符相等了可以发现如果我们不选第 i 个字符实际上和刚刚的推理没什么区别直接可以得出同样的dp[i][j][k][0]dp[i-1][j][k][0]dp[i-1][j][k][1]这个 dp[i][j][k][0] 的推导比较简单而这个 dp[i][j][k][1] 的推导就稍微有点复杂了。正如我们刚刚所说这个第 i 个字符选没选和上一个字符选没选很重要决定着我们从哪里开始结束或者新开一个子串。我们想一想既然现在我们已经选了第 i 个字符了如果说第 i 个字符和上一个字符无关换句话说这第 i 个字符自己是一个新子串的开头了那这样一来上一个字符选没选同样没关系了上一个字符就可选可不选。上一个字符既可以不被选入子串也可以作为上一个子串的结尾。但这次不一样了因为这个字符 i 代表这一个新子串所以说它占掉一个子串选择名额留给前面 i-1 个字符的就只有 k-1 个选择了。而且由于 A[i]B[j] 它们目前是匹配在一个子串里的按我们的逻辑应该是前面 i-1 个和 j-1 个进行子串选择组合匹配了因为结尾的就是同一个新子串里的所以上一个状态应该是dp[i-1][j-1][k-1][0] 和 dp[i-1][j-1][k-1][1] 。所以目前我们得到一个式子dp[i][j][k][1]dp[i-1][j-1][k-1][0]dp[i-1][j-1][k-1][1]但不能忘了我们还有一种情况。如果这个字符 i 不是一个新子串开头而是紧接着上一个子串的末尾呢这个时候上一个字符也是必然属于一个子串里的是必被选的。而且这样的话这个字符 i 就没有占掉了我们要求的 k 个子串名额了。所以 k 个子串选择要留给了前 i-1 个字符。所以应该由状态dp[i-1][j-1][k][1]推导而来。所以最终我们可以得到dp[i][j][k][1]dp[i-1][j-1][k-1][0]dp[i-1][j-1][k-1][1]dp[i-1][j-1][k][1]细节问题状态转移方程推导完成后其实这道题就没什么难度了。但是我们还需要注意几个问题。首先就是这题的dp 数组初始化问题了由于这题的状态定义非常复杂所以初始化的时候我们也会有点头晕了我们必须好好去分析。毫无疑问dp[0][0][0][0] 肯定是要初始化为 1 的。dp[0][0][0][1]呢其实在前两维为 0 的情况下这个点根本就没存在意义不用管了。我们再回忆一下我们的 dp 状态定义如果表示字符串 B 的那一维为 0 也就是所有 dp[i][0][0][0] 也要全部初始化为 1 。因为在状态的定义上在字符串 A 的前 i 个字符选出 0 个子串而且不选第 i 个组合起来等于字符串 B 是成立的而在逻辑上初始化 dp[i][0][0][0] 为 0 也代表着我们其实前 i 个字符都不选为子串也是符合逻辑的可以做到的。初始化的问题必须理清楚了一旦漏了初始化很多地方都会出错还找不出错误的地方......其次就是这道题想要 AC 可没这么简单。我们注意我们开的数组是四维的。一般 dp 数组来到三位四维这个位置及以上我们就几乎必须考虑进行滚动数组的优化了。我们可以发现我们的每一个关于 i 的状态都只用到了前一个 i-1 的状态推导而来所以滚动数组是完全可行的。如果不用滚动数组我们开的 dp 数组就是 dp[1005][205][205][2] 了。计算下来如果是 int 类型我们直接用掉了大约322 MB内存了必然 MLE 。所以滚动数组优化几乎是必须的了。如果有对滚动数组不那么精通的读者可以去看看我之前的一个专门讲解清楚滚动数组优化的方式的博客。链接https://blog.csdn.net/h_a_o777oah/article/details/159437257代码及总结由于本人较菜所以滚动数组我写得更好理解一点的奇偶滚动数组感觉类似 01 背包的滚动数组写法还是有点难理解。以下是本人的代码。#include bits/stdc.h #define int long long//我用个long long怕不知道哪里爆了虽然有取模 using namespace std; const int mod1000000007;//记得取模 int dp[2][205][205][2];//dp数组 void solve(){ int n,m,k; cinnmk; string a,b; cinab; //我对字符串a和b都做了一点下标偏移让下标从1开始而不是0开始更符合直觉 a a; b b; dp[0][0][0][0]1; //遍历三层 i,j,h for(int i1;ia.size();i){ int nii1; int bi(i-1)1; dp[ni][0][0][0]1;//滚动数组每一次都得记得初始化 for(int j1;jb.size();j){ for(int h1;hk;h){ //写下刚刚推导得出的状态转移方程 if(a[i]!b[j]){ dp[ni][j][h][0](dp[bi][j][h][1]dp[bi][j][h][0])%mod; dp[ni][j][h][1]0; }else{ dp[ni][j][h][0](dp[bi][j][h][1]dp[bi][j][h][0])%mod; dp[ni][j][h][1](dp[bi][j-1][h-1][0]dp[bi][j-1][h-1][1]dp[bi][j-1][h][1])%mod; } } } } cout(dp[n1][m][k][1]dp[n1][m][k][0])%mod\n;//最终答案选和不选最后一个字符都要算上 } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int T1; while(T--){ solve(); } }全部看下来这道题主要的价值就是我们能否想到将当前这个字符 i 选不选这个状态变成 0 和 1 放入 dp 数组里。理解了这个对我们后续做题会更有好处。还有就是在高度复杂的 dp 状态里处理初始化问题这个不静下心想想真的很容易漏掉。我一开始就只想到了 dp[0][0][0][0]1没想到全部 dp[i][0][0][0] 都应该等于 1 。推导状态转移相比起来就容易很多了但还是需要认真思考第一次做不出来很正常以后第二次碰到类似的想必能马上推导出来的。洛谷P2331题目链接P2331 [SCOI2005] 最大子矩阵 - 洛谷经过刚刚那道题我们看到这个题目就可能有点似曾相识的感觉了。一样都是选择 k 个只不过一个是矩阵一个是子串。但很明显这题的相比于刚刚的就更加复杂了。矩阵和子串完全不是一个难度的东西子串我从头扫到尾就行了可是矩阵呢我要多大的长宽而且随便想想都能发现这一推导下来好像完全没有什么办法进行任意矩阵的状态转移。但是这也不是完全没有任何办法去做。相信仔细观察都能发现这题的m 限制要么是 1 要么是 2。这就给了我们一点希望了。如果 m 等于 1 那这题和刚刚的选择子串不是几乎一模一样的吗唯一需要处理的就是 m 等于 2 的情况了。我一开始确实发现了 m 的限制特殊可我一下也没反应过来应该分开两种情况来写下意识以为要写一个同时适用于 m 两种情况的写法。但是其实面对这种情况限制较少的完全可以考虑分开两种情况 m1 和 m2 来分别设计适合的方法。情况一 m 1如果 m 等于 1 实际上就是和刚刚的子串选择无异了。相对来说甚至更加简单。因为本质上选择子串和选择子矩阵都是连续区间的嘛所以方法也是共通的。我们只需要如下 dp 数组定义就能很快做出来了。1. dp[i][j][0] 在前 i 个数字里选择 j 个子矩阵且不选择第 i 个数字。2. dp[i][j][1] 在前 i 个数字里选择 j 个子矩阵且选择第 i 个数字。比刚刚更加简单了这里只有三个维度数组只要按照刚刚子串的思路去推导状态转移方程即可。由于相对比较简单不再赘述我们重点看 m2 的情况。情况二 m 2如果 m 等于 2 情况就似乎很复杂了。如果沿用刚刚 dp[i][j] 代表前 i 个数字选择 j 个子矩阵显然状态还不够我们需要得知最后的那个位置 i 我们是一个怎么个选择的情况。现在 m2 了我们的最后位置 i 就有了两个数字而他们分别可能处于什么状态呢看起来很复杂其实我们梳理清楚会发现实际上它们只可能有五种状态关系。为了描述得更直观在最后位置 i 的其中一个数字叫数字 a 另一个数字叫数字 b。大家看的时候建议还是拿笔出来画一下否则纯看可能有点难理解。以下是五种状态的罗列。为了符合数组下标我会从下标 0 开始。状态 0 a 和 b 都不被选入子矩阵中。状态 1 a 被选入了子矩阵中但 b 没有被选入。状态 2 a 没有被选入子矩阵但是 b 被选入了。状态 3 a 和 b 都被选入了子矩阵中但是它们不属于同一个子矩阵。状态 4 a 和 b 同时被选入了同一个子矩阵中。事实上我们的选择情况就只有这五种状态而已不会再有其他状态了。所以我们既然发现了状态其实就这几个我们完全可以直接在 dp 数组新开一维表示状态 0-4。最终我们的 dp 数组定义就可以直接确定了。dp[i][j][k] 在前 i 个数字里选择出 j 个子矩阵且目前最后位置 i 的两个数字处于状态 k 。这些状态实在非常复杂我们需要一个个去推导才行。所以做题还是推荐把状态 0-4 分别代表什么写在纸上这样就不会绕晕了。状态 0回忆一下状态 0 代表的是 a 和 b 都不被选入子矩阵中。那既然 a 和 b 都和我们的子矩阵无关了那它上一个状态 i-1 就可以是 0-4 的任意一个状态了。而且 a 和 b 没有占任何子矩阵的名额。所以答案很简单。dp[i][j][0]max( dp[i-1][j][0] , dp[i-1][j][1] , dp[i-1][j][2] , dp[i-1][j][3] , dp[i-1][j][4] )状态 1状态 1 我们选择了数字 a 所以我们就要记得把这个对应的数字加入 dp 值里了。但是我们还需要注意一个问题选择的数字 a 到底是承接上一个子矩阵还是它自己单独成为一个子矩阵的开头如果它要单独做一个子矩阵的开头那么其实上一个状态 i-1 选择什么同样和它无关了可以是状态 0-4 任意一个。唯一不同的是它占掉了一个子矩阵的选择名额所以上一个状态应该变成 j-1 了。dp[i][j][1]max( dp[i-1][j-1][0] , dp[i-1][j-1][1] , dp[i-1][j-1][2] , dp[i-1][j-1][3] , dp[i-1][j-1][4] ) a如果说它要承接上一个子矩阵那我们就能知道那上一个状态中就必须要选择数字 a 了而数字 b 就是可选可不选。根据定义符合情况的只有 1 和 3 。十分要注意的是 4 绝对不行因为状态 4 中 a 和 b 是属于同一个矩阵的。如果由状态 4 推导而来那我们的矩阵就会变成如下图。这样绝对不符合矩阵的定义不合法。所以我们还有两个状态不能遗漏了。dp[i][j][1]max( dp[i-1][j][1] , dp[i-1][j][3] ) a综合起来即可。状态 2状态 2 是只选 b 不选 a 实际上和状态 1 没什么区别。首先是如果是新开子矩阵与之前状态无关和状态 1 的推导是一样的。dp[i][j][2]max( dp[i-1][j-1][0] , dp[i-1][j-1][1] , dp[i-1][j-1][2] , dp[i-1][j-1][3] , dp[i-1][j-1][4] ) b如果与之前状态有关是承接上一个子矩阵那也是只有 2 和 3 状态是符合的切记状态 4 不会符合和状态 1 的时候原理一样。dp[i][j][2]max( dp[i-1][j][2] , dp[i-1][j][3] ) b状态 3重要易错状态 3 就稍微复杂了。主要是 a 和 b 是各自为政的我们很容易会漏掉一些情况首先就是a 和 b 都与前面的无关都是新开矩阵那么上一个的状态和刚刚完全一样就和它毫无关系了。但是要注意的是这样一来我们 a 和 b 都会各自占据一个子矩阵名额那就是留给前面的 i-1 就只有 j-2 个了。写代码的时候我们也要记得加上判断 j2 否则就越界访问数组了。dp[i][j][3]max( dp[i-1][j-2][0] , dp[i-1][j-2][1] , dp[i-1][j-2][2] , dp[i-1][j-2][3] , dp[i-1][j-2][4] ) a b如果a 和 b 都是与前面有关的承接之前的子矩阵那也就是说前面的 i-1 状态的 a 和 b 也要被选择而这种情况下只有状态 3 和 4 。而很明显状态 4 是不符合逻辑的。所以这种情况只能由上一次的状态 3 转移而来。而且我们是没有消耗子矩阵划分名额所以 j 不用变。但是由于这种情况下按照逻辑 j 起码也要大于 2 了所以我们最好还是写入判断 j2 的 if 判断里。dp[i][j][3]max( dp[i-1][j][3] ) a b而还有一种情况就是a 和 b 之中有一个和之前的有关承接之前的子矩阵而另一个是自己新开一个矩阵。这样就有点复杂了。首先我们确定我们这种情况会有一个新开矩阵那么留给之前的子矩阵名额就只有 j-1了。那么很好发现如果是 a 是新开的那个子矩阵那么来源状态可以是dp[i-1][j-1][1] 和 dp[i-1][j-1][3]如果 b 是新开的子矩阵那么来源状态就是dp[i-1][j-1][2] 和 dp[i-1][j-1][3]。所以我们这个情况的状态转移方程就是dp[i][j][3]max( dp[i-1][j-1][1] , dp[i-1][j-1][2] , dp[i-1][j-1][3] ) a b状态 3 的情况很容易遗漏我在状态 3 这里就出错了所以这个状态 3 的推导还是比较重要的一定要找到所有情况。状态 4状态 4 就比较简单了首先还是选择的 a 和 b 作为一整个新子矩阵它们占掉一个子矩阵名额且与之前的无关可以由之前的任意状态推导而来。dp[i][j][4]max( dp[i-1][j-1][0] , dp[i-1][j-1][1] , dp[i-1][j-1][2] , dp[i-1][j-1][3] , dp[i-1][j-1][4] ) a b状态 4 里 a 和 b 是绑定一块的所以它如果是承接于上一个状态那么只能是同时都于上个状态有关而且上个状态也只能是状态 4 了。如果上个状态是状态 3 显然不合理。dp[i][j][4]max( dp[i-1][j][4] ) a b代码及总结最终我们的状态推导就完成了。可以看到我们的状态推导出来还是挺多东西的所以我做题写的时候还要写上注释不然写着写着都不知道写到哪了。而且 m1 和 m2 的两种情况实际上用到的数组差不多我们可以按照 m2 这么大的数组开出来 m1 利用其中部分就行了。初始化也是和刚刚的字串一样必须注意这些细节。以下是我的代码。#include bits/stdc.h using namespace std; const int maxn2e55; int dp[105][15][5]; int arr[105][2];//arr[i][0]是a,arr[i][1]是b,m1的时候只用arr[i][0] void solve(){ int n,m,k; cinnmk; memset(dp,0xc0,sizeof(dp));//求最大值全部初始化为0 for(int i0;in;i) dp[i][0][0]0;//初始化 //m1和子串的逻辑基本一样 if(m1){ for(int i1;in;i){ cinarr[i][0]; } for(int i1;in;i){ for(int j1;jk;j){ dp[i][j][0]max(dp[i-1][j][0],dp[i-1][j][1]); dp[i][j][1]max(max(dp[i-1][j-1][0],dp[i-1][j-1][1]),dp[i-1][j][1])arr[i][0]; } } coutmax(dp[n][k][0],dp[n][k][1])\n; }else{ //m2的状态极多一定要分清楚 for(int i1;in;i){ cinarr[i][0]arr[i][1]; } for(int i1;in;i){ for(int j1;jk;j){ //状态0 for(int h0;h5;h) dp[i][j][0]max(dp[i][j][0],dp[i-1][j][h]); //状态1新开矩阵与上一个无关 for(int h0;h5;h) dp[i][j][1]max(dp[i][j][1],dp[i-1][j-1][h]arr[i][0]); //状态1与上一个有关 dp[i][j][1]max(dp[i][j][1],max(dp[i-1][j][1],dp[i-1][j][3])arr[i][0]); //状态2与上一个无关 for(int h0;h5;h) dp[i][j][2]max(dp[i][j][2],dp[i-1][j-1][h]arr[i][1]); //状态2与上一个有关 for(int h2;h4;h) dp[i][j][2]max(dp[i][j][2],dp[i-1][j][h]arr[i][1]); //状态3 if(j2){ //状态3与上一个同时无关 for(int h0;h5;h) dp[i][j][3]max(dp[i][j][3],dp[i-1][j-2][h]arr[i][1]arr[i][0]); //状态3与上一个同时有关 dp[i][j][3]max(dp[i][j][3],dp[i-1][j][3]arr[i][1]arr[i][0]); } //一个有关一个无关 dp[i][j][3]max(dp[i][j][3],max(dp[i-1][j-1][1],max(dp[i-1][j-1][3],dp[i-1][j-1][2]))arr[i][1]arr[i][0]); //状态4与上一个无关 for(int h0;h5;h) dp[i][j][4]max(dp[i][j][4],dp[i-1][j-1][h]arr[i][1]arr[i][0]); //状态4与上一个有关 dp[i][j][4]max(dp[i][j][4],dp[i-1][j][4]arr[i][1]arr[i][0]); } } int ans-1e9; for(int i0;i5;i) ansmax(ans,dp[n][k][i]);//从5种状态中得出最大值 coutans\n; } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int T1; //cinT; while(T--){ solve(); } }总结下来这两道题目其实都是差不多类型的 k 个划分 DP 。而且基本都是要求我们在 DP 的时候要记录状态。比如 P2331 中就可以直接用几个数字来代表所属的状态了。特别之后看到这种类似选 k 次且当前决策会锁定后续连通性的题目其底层逻辑必然坍缩为状态机映射。希望大家看完可以彻底明白这种 DP 的思维
