一个整数n表示需要得到的表情数
一个整数ans表示最少需要的操作数
233
17
思路：（从大佬博客里抄袭的）
让我们先来考虑最暴力的做法，同时记录当前已有数字和剪切板中的数字，直接记忆化搜索，三种转移就不用我再多说了吧。倘若在这道题目上硬要想出什么性质的话恐怕有些困难（也许我太弱了），这就要用到这道题目中最关键的一个思想了——输出中间过程，观察其性质。
不妨让我们来记录一下当前数字是由哪个状态转移过来的，尽管记忆化搜索能跑出来的数据范围比较小，但是再加上我们人类智慧的逻辑推理我们便可以得到过程实际上是这样的（注意x仅代表未知数，不代表具体几次，更不代表其次数相等）：
其实也很好想吧，连续两次的复制显然是没有意义的，而复制后的退格也可以放到粘贴后面从而对最终得到的结果没有影响，（就这样我用搜索才想到了一个别人可以一眼秒出的结论）既然如此我们为什么不把复制和粘贴看做一个整体呢？于是简化版题意如下：
观察到题目中的操作无非就是由一个数转化到另一个数的时候要付出代价，要求最小化代价。为什么模型好像这么熟悉？经典的最短路模型！连边1：x−>x∗k，连边2：x−>x−1，显然连边数量太庞大了，我们来考虑优化。关键就在于连边1比较恐怖，但我们仔细想想就会发现里边存在大量冗余边。考虑将一个数标准分解k=pa11pa22...，既然我们可以多次复制，为什么我们还需要复制一次后一步步跳到x∗k上去呢（也就是a1∗p1+a2∗p2+...<=k）？由此我们又得到一个优化：连边1转化为只向x∗p连边（p是质数），对结果一定没有影响。
然后我们似乎遇到了瓶颈，好像没有什么优化的方法了，但这时一定要坚定信念，这道题也是出题人出的呀，他又没有用什么量子计算机来使程序跑得更快，所以直觉告诉我们一定还存在优化！还记得之前说过做这道题需要的重要思想吗？没错，我们再把最短路的转移过程给输出出来！一个神奇的结论在中间过程中显现了出来：①我们只会用到{2,3,5,7,11}这几个数连出去的边（当然事实上我们用到的貌似还可以更少，但是这就已经够了）（前4个质数会在最小120241处出错）（别问我证明，我并不会）。②退格操作不会连续出现4次以上（别问我证明，我并不会）。这样我们就又减少了大量的冗余边，对于0.4秒我们已经可以出解了。我的比较丑陋的代码（懒得删掉调试信息了）（我们的优化还没有结束！如果想知道的话请看代码下方）：
#include<iostream>
#include<cstdlib>
#include<queue>
#include<cstdio>
#include<cstring>
#define MAXN 1000010
using namespace std;
queue<int>que;
int n;
int p[]={,,,,,};
int dis[MAXN],vis[MAXN];
void spfa(int s){
memset(vis,,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
while(!que.empty()) que.pop();
que.push(s);
dis[s]=;vis[s]=;
while(!que.empty()){
int now=que.front();
que.pop();
vis[now]=;
for(int i=;i<;i++){
if(now*p[i]<n+&&dis[now*p[i]]>dis[now]+p[i]){
dis[now*p[i]]=dis[now]+p[i];
if(!vis[now*p[i]]){
vis[now*p[i]]=;
que.push(now*p[i]);
}
}
}
if(dis[now-]>dis[now]+){
dis[now-]=dis[now]+;
if(!vis[now-]){
vis[now-]=;
que.push(now-);
}
}
}
}
int main(){
scanf("%d",&n);
spfa();
cout<<dis[n];
}