前置芝士

STL：pair,map，简单 dfs，记忆化剪枝，重载运算符。

题目大意

给你一个字符串，重复的字符串可以用字符 $R$ 和字符 $M$ 配合减少一半（减了还可以减），求最后剩余字符串的最小长度。

分析

很多人都说，搜索可以拿到部分 pts，但这题的正解是区间/线性 DP， 作为一名懒得想状态转移方程的蒟蒻，考虑用搜索骗分，三个操作：

• 在这里加一个 M，重置缓冲串。
• 从这里开始复制缓冲串，注意要满足前提条件（这里引进一个简单便捷的函数：substr， name.substr(i,len) 返回值为 string 类型）。
• 直接将字符加进缓冲串。

模拟就完啦，简单易懂的搜索。

直接模拟时间复杂度是 $O(3^n)$ ，显而易见的 TLE...考虑记忆化剪枝，这里的记忆化数组由搜索的参数决定，有两个参数：1、字符对应的下标；2、缓冲串。所以记忆化数组有两维，但是我们会发现有一维是字符串类型的，这里有三种做法：

1. 存字符串的 Hash 值；
2. 存对应数组下标；
3. 存字符串。

这里只讲第 $3$ 种做法，这里就要用我们的 map，map 是一种十分好用的 STL，它是一种键与值两两搭配构成的 STL，可以快速查询给出的键对应的值是什么，键和值均可以为其他数据结构或结构体，这里我们用 pair<int,string> 作为键，操作次数作为值，这样就可以记忆化啦！但是 map 需要对键做一个排序(为了更快的查询)，这就要用到我们的重载运算符了，这个其实很简单，就不展开讲，注意，map需要的运算符是小于符号，别重载错了。

该讲的都讲完了，上代码!

#include <bits/stdc++.h>
#define i first
#define hc second
using namespace std;
typedef pair<int ,string> node;//定义键的类型 
bool operator<(node x,node other){//重载运算符 
	return x.i<other.i||(x.i==other.i&&x.hc<other.hc);//这里只是乱排了个序，对查询无任何影响qwq 
}
map<node,int> dp;//定义记忆化容器 
int n;
string s;
int dfs(int i,string hc){
	if(i==n) return 0;//搜索出口 
	if(dp.find(node(i,hc))!=dp.end()) return dp[node(i,hc)];//dp.find(x)为查询dp与x对应的键的位置，若没有，则返回dp的尾指针，即dp.end() 
	int Min=dfs(i+1,hc+s[i])+1;//字符串+字符(串)是将后面的字符(串)拼接在前面的字符串后面 
	if(hc.length()) Min=min(Min,dfs(i,"")+1);// ""为空字符串 
	if(hc.length()&&hc==s.substr(i,hc.length())) Min=min(Min,dfs(i+hc.length(),hc+hc)+1);
	return dp[node(i,hc)]=Min;
}
int main() {
	cin >> s;
	n=s.length();
	printf("%d\n",dfs(0,""));
	return 0;
}

https://blog.csdn.net/tenkuo/article/details/154691671