试题：最优包含

题目描述：

我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。
给定两个字符串 S 和 T，请问最少修改 S 中的多少个字符，能使 S 包含 T ？

其中， 1 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 1000 ， 1 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 10001 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 1000 ， 1 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 1000 1 \leq |T| \leq |S| \leq 1000，1≤∣T∣≤∣S∣≤10001≤∣T∣≤∣S∣≤1000，1≤∣T∣≤∣S∣≤1000 1≤∣T∣≤∣S∣≤1000，1≤∣T∣≤∣S∣≤10001≤∣T∣≤∣S∣≤1000，1≤∣T∣≤∣S∣≤1000。

解析：

这道题目，首先，我们先不看正确的答案，然后我们自己写一个dfs看看。毕竟dfs是万能的（笑）。
我们设dfs（N，M）的意思是：对S的字符串的0->N-1和T字符串的0->M-1。安装题目的要求，存入修改多少个S中的字符满足题意的那个数字（或者说是return这个数字）。
现在字符串的下标不是从0开始，而是从1开始。我的习惯就是如此。
那题目的答案就是求出dfs（S.length，T.length）

dfs的思想是，本层和下一层（或上一层）。我们现在本层是（9，5）：可以理解为：一个指针指在S[9]一个指针指在T[5]。那么我们上一层（因为我觉得说上一层更符合思想）就是指针分别往前移动。请往下看，来理解。

比如我们看题目中的样例，那么最终答案就是dfs(9,5)
那我们怎么求dfs(9,5)呢？
如果S[9]==T[5]。这种状态跟dfs(8,4)是一模一样的，因为我们根本就不需要做S的修改。所以dfs(9,5)==dfs(8,4)

但是しかし，非常的遗憾通知您，S[9]！=T[5]那我们怎么办呢？
（1）[修改S字符串方法] ：我们可以修改S[9]为为“Z”，那么现在dfs(9,5)==dfs(8,4)+1。（别忘记我们规定的dfs的含义。现在我S[9]和T[5]我都不选择，然后改变一个S[9]为“Z”在次转移到dfs(9,5)现在就包含了S[9]和T[5]）。

（2）[不修改S字符串的方法] ：我们可以试探一下dfs(8,5)也就是看看：
紫色圈圈圈出的这部分，能不能得到答案。如果dfs(8,4)返回一个巨大无比的数字，我们就认为是之前不能搞出一个解的。也就是如果不修改字符串S就是行不通的。

最后：dfs(9,5)=min(dfs(8,4)+1,dfs(8,5));

考虑边界：
（1）|S|<|T|：无论S怎么修改都不可能配出T字符串，因为S长度太短了。
（2）|T|==0：T字符串是一个空串，不需要修改字符串S了。

正解dfs代码：

#include <cstring>
#include <iostream>
using namespace std;
string S, T;
int S_len, T_len;
int dfs(int s_p, int t_p) {
    if (t_p > s_p) {
        return 9999999999;
    }
    if ((s_p == 0 && t_p == 0) || t_p == 0) {
        return 0;
    }
    if (S[s_p] == T[t_p]) {
        return dfs(s_p - 1, t_p - 1);
    } else {
        return min(dfs(s_p - 1, t_p - 1) + 1, dfs(s_p - 1, t_p));
    }
}
int main() {
    cin >> S >> T;

    S.insert(S.begin(), ' ');  //手动将S和T的下标从1开始。
    T.insert(T.begin(), ' ');

    S_len = S.length() - 1;  //记录一下S和T字符串的长度，不要忘记前面的''
    T_len = T.length() - 1;

    cout << dfs(S_len, T_len);
    return 0;
}

解析2：

说到这里，你一定会发现，其实dfs运算是很浪费的，因为会对同一个点（s_p，t_p）进行访问多次。所以我们想到了状态缓存，也叫动态规划。（淦，为什么叫动态规划其实我也不明白为什么）
然后其实我们当时推出dfs的递归公式的时候，也就把dp的公式给推到出来了，简直就是一模一样，我们稍微改写：

正解代码（动态规划）：

#include <cstring>
#include <iostream>
using namespace std;
string S, T;
int S_len, T_len;
int dfs[1001][1001];
int main() {
    cin >> S >> T;

    S.insert(S.begin(), ' ');  //手动将S和T的下标从1开始。
    T.insert(T.begin(), ' ');

    S_len = S.length() - 1;  //记录一下S和T字符串的长度，不要忘记前面的''
    T_len = T.length() - 1;

    dfs[0][0] = 0;                          //边界嘛。
    for (int i = 1; i <= S_len; i++) {      // S_p
        dfs[i][0] = 0;                      //和dfs是一样的。因为T为0，那么S根本就不用修改
        for (int j = 1; j <= T_len; j++) {  // T_p
            if (j > i) {
                dfs[i][j] = 999999999;  //这里赋值这么大，是因为为了下一层有可能访问到TA，所以搞大一点。
                continue;
            }
            if (S[i] == T[j]) {
                dfs[i][j] = dfs[i - 1][j - 1];
            } else {
                dfs[i][j] = min(dfs[i - 1][j], dfs[i - 1][j - 1] + 1);
            }
        }
    }
    cout << dfs[S_len][T_len];
    return 0;
}

吐槽一句：我这里建议蓝桥杯直接改名字好啦，改成动态规划杯，嘻嘻嘻（我可是一只调皮的熊哦~）

试题：排列数

题目描述：

题意

在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。

对于一个 1 ∼ n 的排列，如果可以将这个排列中包含 t 个折点，则它称为一个 t + 1 单调序列。 例如，排列 (1,4,2,3)(1,4,2,3)(1,4,2,3) 是一个 3 单调序列，其中 4 和 2 都是折点。 给定 n 和 k，请问 1 ∼ n 的所有排列中有多少个 k 单调队列？

输入输出描述

输 入 一 行 包 含 两 个 整 数 n , k ( 1 ≤ k ≤ n ≤ 500 ) n , k ( 1 ≤ k ≤ n ≤ 500 ) 。 输入一行包含两个整数 n,k (1≤k≤n≤500)n,k(1≤k≤n≤500)。 输入一行包含两个整数n,k(1≤k≤n≤500)n,k(1≤k≤n≤500)。

输出一个整数，表示答案。答案可能很大，你可需要输出满足条件的排列数量除以 123456 的余数即可。

输入输出样例

输入：4 2

输出：12

分析：

高中数学回顾：

本题目是排列组合问题，依旧是一个动态规划的问题。

首先排列组合本身就是一个动态规划。
比如我们有3个数，1，2，3。总共可以组合6种不同位置的数字。
比如：123 132 312 213 231 321

我们高中学过一个公示，如果有n个数子，那么它的排列数（全排列）是 n ！ n！ n！。比如上面的3个数字的全排列就是 1 ∗ 2 ∗ 3 1*2*3 1∗2∗3。

为什么是这个样子呢，比如我们看数字“3”是怎么排列的。
（1）我们可以先排列前两个数字1 2总共两种可能：1 2 2 1
（2）然后我们插入3到空隙中。(空隙)1(空隙)2(空隙)然后变成3 1 2 1 3 2 1 2 3而(空隙)2(空隙)1(空隙)也是一模一样的样子。所以最后是6种。

也就是，前2个数字有2种方法，而前2个数字每种方法有3个空隙，所以直接 2 ∗ 3 2*3 2∗3。（数字1只有一种位置可以放，所以最终 1 ∗ 2 ∗ 3 1*2*3 1∗2∗3）

题目解析：

现在，我们来看看这道题目吧！

假设我们现在有一个序列，它是拥有3个折点。

不过在继续下一步之前，我想先定义一些东西：

然后我们现在思考：
（1）三个折点可以全部是突折点或者凹折点吗？
这是不可能的，这是因为两个凸折点链接在一起，一定会产生一个凹折点。同理的，两个凹折点链接在一起会产生一个凸折点。
所以：当折点的个数是偶数的时候，凸折点和凹折点的个数应该是一样的。而当折点的个数是奇数的时候。要么有折点总数 整除 2个凸折点或者凹折点，剩下的就是凹折点或者凸折点。

（2）折点个数为3的序列大体看上去是什么样子的？
现在我们有5个数字，1，2，3，4，5。如下图，下图有三个折点。
（作图软件：Ms PowerPoint）

当然，下面的这张图片也有3个折点：

那么总体来说：从远处看，我们可以看到的就是这两种情况：
（作图软件：画图）

但是如果现在不仅仅有6个数字，而有很多个位置呢？
其中实心黑色的地方就是数字存在的位置。

（3）动态规划该怎么转移呢？

增加0个凸点：

比如现在，我们在往后面加上一个数字，这个数字比前面的所有数字都要大。
现在我们设置状态数组d p [ N ] [ M ] p[N][M] p[N][M]表示：前N个数字（这些数字从小到大排列）然后M表示折点的个数。

（参照上面用Ms PowerPoint画出的图片）
首先需要理解 d p [ 5 ] [ 3 ] dp[5][3] dp[5][3]是包含了全部的M和W这样形状的全部组合的个数。如果我们递推是正确的话，您完全不用担忧 d p [ 5 ] [ 3 ] dp[5][3] dp[5][3]存放的是错误的答案。所以就请相信，里面存放了所有的W和M形状的组合的个数吧！

现在看看第六个数字插入的位置。
插入在No.X位置上的数字六不会对折点的个数有一点点的影响。
插入No.2和No.3位置上的数字六也不会对折点产生影响。
（总共4个位置，这种情况有一个凸点）

而M形状的也是同样的情况：

还是4个点。（这时候有两个凸点，一个凸点就会产生两个这样拆入却不增加折点的空隙，上上图中虽然只有一个凸点，但是它左右两边是上升的，所以还是不会增加凸点。）

偶数凸点也是一样哦，请自己在纸上画一画。

所以我们最终找到的规律是：增加0个折点的方法是： M / 2 ∗ 2 + 1 M/2*2+1 M/2∗2+1
(M是上面定义的dp数组的折点的个数）

增加1个凸点：

偶数折点也是同样的，请读者自行验证。

增加3个折点：

那么就是前面所有的空隙排除“增加0个折点和增加1个折点”的空隙剩下的位置。

可能说的比较乱上面的话，我的意思就是，找出所有能增加两个折点的空隙。

（N设实心点的个数，M是折点的个数，还记得我们定义的dp公式吗？）
那么就是N个实心点，有N-1个空隙。

然后N个节点，只考虑在n个节点直接的空隙，在n节点之外的空隙，比如最前和最末尾不在考虑范围之内。
总共 N − 1 N-1 N−1减去红色的点（折点+0） M / 2 ∗ 2 M/2*2 M/2∗2在减去橙色的点（折点+1）有一个。

最终化简为 N − M − 2 N-M-2 N−M−2。

其他位置还请读者自行思考。（笑）
（图片来源：蓝桥杯官方教材“决赛训练营”https://www.lanqiao.cn/courses/3981/learning/?id=134743）

现在我们有了终极递推式：
d p [ i + 1 ] [ j ] + = d p [ i ] [ j ] ∗ ( j + 1 ) ; dp[i+1][j] += dp[i][j] *(j+1); dp[i+1][j]+=dp[i][j]∗(j+1);
​ d p [ i + 1 ] [ j + 1 ] + = d p [ i ] [ j ] ∗ 2 ; dp[i+1][j+1] += dp[i][j]*2; dp[i+1][j+1]+=dp[i][j]∗2;
​ d p [ i + 1 ] [ j + 2 ] + = ( d p [ i ] [ j ] ∗ ( i − j − 2 ) ) ; dp[i+1][j+2] += (dp[i][j]*(i-j-2)); dp[i+1][j+2]+=(dp[i][j]∗(i−j−2));

正解代码：

#include<cstdio>
#include<iostream>

using namespace std;
const int mod = 123456;
int n, k, dp[1009][1009];

int main() {
    cin >> n >> k;
    dp[1][0] = 1;//一个数字，折点为0个，这样的方案有一种
    for (int i = 2; i <= n; i++) {
        dp[i][0] = 2;//没有这点，要么n个数字单调递增，要不然单调递减，总共两种。
        for (int j = 0; j <= i - 2; j++) {
        //从dp[i][j]往后面的状态推。
            dp[i + 1][j] = (dp[i + 1][j] + (dp[i][j] * (j + 1)) % mod) % mod; //增加0个折点
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + (dp[i][j] * 2) % mod) % mod; //1个折点
            dp[i + 1][j + 2] = (dp[i + 1][j + 2] + (dp[i][j] * (i - j - 2)) % mod) % mod;  //2个折点。
        } 
    }
    cout << dp[n][k - 1] % mod << endl;
    return 0;
}

蓝桥杯，动态规划杯！蓝桥杯，动态规划杯！蓝桥杯，动态规划杯！
感受就是，如果想要考蓝桥杯国赛要拿一个国二，动态规划一定要好好学哦~

试题：解密游戏

题目描述：

题意：

小明正在玩一款解谜游戏。谜题由 24 根塑料棒组成，其中黄色塑料棒 4 根，红色 8 根，绿色 12 根 (后面用 Y 表示黄色、R 表示红色、G 表示绿色)。初始时这些塑料棒排成三圈，如上图所示，外圈 12 根，中圈 8 根，内圈 4 根。

小明可以进行三种操作：

1. 将三圈塑料棒都顺时针旋转一个单位。例如当前外圈从 0 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么顺时针旋转一次之后，外圈、中圈、内圈依次变为：GYRYGRYGRGGG、 YRGRGGRR 和 RGGG。

2. 将三圈塑料棒都逆时针旋转一个单位。例如当前外圈从 0 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么逆时针旋转一次之后，外圈、中圈、内圈依次变为：RYGRYGRGGGGY、 GRGGRRYR 和 GGRG。

3. 将三圈 0 点位置的塑料棒做一个轮换。具体来说：外圈 0 点塑料棒移动到内圈 0 点，内圈 0 点移动到中圈 0 点，中圈 0 点移动到外圈 0 点。例如当前外圈从 0 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么轮换一次之后，外圈、中圈、内圈依次变为：RRYGRYGRGGGG、GGRGGRRY 和 YGGR。

小明的目标是把所有绿色移动到外圈、所有红色移动中圈、所有黄色移动到内圈。给定初始状态，请你判断小明是否可以达成目标？

输入描述：

第一行包含一个整数 T ( 1 ≤ T ≤ 100 ) T (1≤T≤100) T(1≤T≤100)，代表询问的组数。

每组询问包含 3 行：

• 第一行包含 12 个大写字母，代表外圈从 0 点位置开始顺时针每个塑料棒的颜色。
• 第二行包含 8 个大写字母，代表中圈从 0 点位置开始顺时针每个塑料棒的颜色。
• 第三行包含 4 个大写字母，代表内圈从 0 点位置开始顺时针每个塑料棒的颜色。

输出描述：

对于每组询问，输出一行 YES 或者 NO，代表小明是否可以达成目标。

解析：

想法：

这道题目是一道只要求输出“YES”或者“NO”的那一类题型。

这里我参考了一位大佬的方案，想看他的解析请移步：https://blog.csdn.net/m0_45210226/article/details/109634102

那么，我们怎么去思考他呢，我一开始思考的是写一个dfs，不停转动，然后改变次序呗，但是这样复杂度就炸天了。

然后我又想会不会是动态规划，但是没有想出来。后来看了上面大佬的博客，思路一下子就打开了。

首先：您必须明白，到底为什么，游戏会失败，也就是，为什么，配凑不出来。

这是因为，比如内圈的0号位置，它永远只能和中圈的0号位置和4号位置相互交换。不行的话，现在请你拿出两根手指，然后一根指在内圈0号位置，一根指在外圈的0号位置，顺时针转动4下，然后再转动4下。之后，你就明白我说的意思了。

好的，现在我们知道：

(1)如果现在他们颜色全部为黄色（或其他同一种颜色），那么永远不可能交换出正确的颜色。游戏无效。

(2)如果现在有两个黄色，也是不正确的，因为实在不能将所有的黄色都排在一个内圈的位置上，总有一个黄色会留在外圈。游戏无效。

(3)所以，最好的情况是，只有一个黄色，然后可以放进“内圈0号位置”。

但是不要忘记：我们还有一个外圈没有考虑，但是实际情况是一样的。
（图片引用自：https://blog.csdn.net/m0_45210226/article/details/109634102）

外圈对应3个位置。请看图片。然后按照这样子划分区域的话，总共能画出4大类。
上面的蓝色是一类。
上图就是对应的四大类。
每种类型必须要求有且只有“1个黄色”“2个红色”“3个绿色”。要不然就是怎么操作都满足不了游戏的要求。

正确性验证：

现在我们定义N_M当N=1，2，3的时候分别代表 内圈 中圈 外圈。而M则是位置。
比如1_1代表中圈第一个位置。
现在我们有：

那么（1_0,2_0,3_0)这样的位置都有机会对应一次吗？
如果你朝着一个方向循环6次，那么上面所有的位置都会被对应一次。
手动证明完毕，嘿嘿。

正解代码：

#include<bits/stdc++.h>
using namespace std;
int t;
string s1,s2,s3;
int main(){
	//freopen("a.txt","r",stdin);
	cin>>t;
	while(t--){
		int flag = 0;
		cin>>s3>>s2>>s1; 
		for(int i = 0;i<4;i++){ //分成了四大类
			map<char ,int>mp;
			//内圈 
			mp[ s1[i] ] += 1;
			//中圈
			mp[ s2[i] ] += 1;
			mp[ s2[ i+ 4]] += 1;
			//外圈
			mp[ s3[i] ] += 1;
			mp[ s3[ i+4]]  += 1;
			mp[ s3[i+8]] += 1;
			
			if(mp['Y'] != 1 || mp['R'] != 2 || mp['G'] != 3){
				flag = 1;
				break;
			}		
			
		}
		if(flag == 0)
			cout<<"YES"<<endl;
		else{
			cout<<"NO"<<endl;
		}
		 
	}
	return 0;
}