RC-u4 变牛的最快方法
思路
最短编辑距离+记录路径板子题，不懂最短编辑距离的可以看看网上的博客。不懂为什么官方题解用的bfs写法，然后网上所有的题解就是bfs了。我这里就是双重for循环实现，参考下写法即可。
代码
点击查看代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PII pair<int,int>
using namespace std;
const int N = 1e3+9;
int a[N],b[N],n,m,dp[N][N],op[N][N];
PII pre[N][N];
int main() {
int xx;
while(cin>>xx&&xx!=-1) a[++n]=xx;
while(cin>>xx&&xx!=-1) b[++m]=xx;
memset(op,-1,sizeof op);
//初始化很重要
for(int i=0; i<=n; ++i) dp[i][0]=i,op[i][0]=0,pre[i][0]={i-1,0};//删除
for(int i=0; i<=m; ++i) dp[0][i]=i,op[0][i]=3,pre[0][i]={0,i-1};//插入
for(int i=1; i<=n; ++i) {
for(int j=1; j<=m; ++j) {
int c=(a[i]!=b[j]);
int add = dp[i][j-1]+1;//在a[i]前面添加b[j]
int del = dp[i-1][j]+1;//删除a[i]
int rce=dp[i-1][j-1]+c;//替换a[i]为b[j]
dp[i][j]=min(add,min(del,rce));
if(dp[i][j]==rce) {
op[i][j]=1;//记录操作
pre[i][j]={i-1,j-1};//记录从哪里转移来的，下面同理
if(a[i]==b[j]) op[i][j]=2;
}
else if(dp[i][j]==add) op[i][j]=3,pre[i][j]={i,j-1};
else op[i][j]=0,pre[i][j]={i-1,j};
}
}
cout<<dp[n][m]<<endl;
//从右下角（n,m）根据pre数组，往回找路径
PII t = {n,m};
vector<int> ans;
while(t.x||t.y){
ans.push_back({op[t.x][t.y]});
t=pre[t.x][t.y];
}
reverse(ans.begin(), ans.end());
for(auto &it : ans) cout<<it;
return 0;
}
/*
in:
1 -1
3 2 1 -1
out:
2
332
*/