[暑假集训]开训复健练习赛 B

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 #include<string>
 5 #include<vector>
 6 #include<map>
 7 #include<cstring>
 8 #include<algorithm>
 9 #define DEBUG if(  0  )//方便测试
10 using namespace std;
11 int ind,mark;
12 const int del=0,rep=1,ins=2;
13 int dp[85][85],way[85][85];
14 //dp记录到达此处需要多少操作
15 //way使用小键盘记录方向
16 //8=上(插入) 7=左上(替换) 4=左(删除) 5=无需操作（相当于前后相同的替换）
17 int flen,tlen;
18 string fr,to;
19 string task[10];
20 int TOX[10],TOY[10];
21 void showans(int x,int y){
22     //使用递归，根据way我、方向表来查找操作顺序
23     if(x+y>0){
24         int tt=way[y][x];
25         DEBUG cout<<x<<" "<<y<<" "<<tt<<endl;
26         if(tt==5) {//无需操作
27             return showans(x+TOX[tt],y+TOY[tt]); 
28         }
29         if(tt==4) {
30             //先输出上一步
31             showans(x+TOX[tt],y+TOY[tt]);
32             cout<<dp[y][x]<<task[tt]<<y+1<<endl;
33         }else{
34             showans(x+TOX[tt],y+TOY[tt]);
35             cout<<dp[y][x]<<task[tt]<<y<<","<<to[y-1]<<endl;
36         }
37         
38     }
39 }
40 int main(){
41     int t;
42     task[4]=" Delete ";
43     task[7]=" Replace ";
44     task[8]=" Insert ";
45     TOX[4]=-1;TOY[4]=0;
46     TOX[5]=-1;TOY[5]=-1;
47     TOX[7]=-1;TOY[7]=-1;
48     TOX[8]=0; TOY[8]=-1;//记录方向等
49     while(cin>>fr>>to){
50         memset(dp,0,sizeof(dp));
51         memset(way,0,sizeof(way));
52         //初始化
53         flen=fr.length();tlen=to.length();
54         for(int i=1;i<=flen;i++){dp[0][i]=i;way[0][i]=4;}
55         for(int i=1;i<=tlen;i++){dp[i][0]=i;way[i][0]=8;}
56         int *pw,*pw1;//方便使用
57         for(int ti=1;ti<=tlen;ti++){//填表
58             for(int fi=1;fi<=flen;fi++){
59                 pw=&way[ti][fi];
60                 pw1=&dp[ti][fi];
61                 if(fr[fi-1]==to[ti-1]){
62                     t=0;*pw=5;//说明5--不需要操作
63                 }else{
64                     t=1;*pw=7;//7--进行一次替换
65                 }
66                 *pw1=dp[ti-1][fi-1]+t;
67                 if(dp[ti][fi-1]+1<*pw1){
68                     *pw1=dp[ti][fi-1]+1;*pw=4;
69                     //4--发现进行删除步数更少
70                 }
71                 if(dp[ti-1][fi]+1<*pw1){
72                     *pw1=dp[ti-1][fi]+1;*pw=8;
73                     //8--发现进行插入步数更少
74                 }
75             }
76         }
77         DEBUG{//输出图表
78             for(int i=0;i<(flen+1)*(tlen+1);i++){
79                 cout<<dp[i/(flen+1)][i%(flen+1)]<<" ";
80                 if(i%(flen+1)==flen)cout<<endl;
81             }
82             cout<<endl;
83             for(int i=0;i<(flen+1)*(tlen+1);i++){
84                 cout<<way[i/(flen+1)][i%(flen+1)]<<" ";
85                 if(i%(flen+1)==flen)cout<<endl;
86             }
87         }
88         cout<<dp[tlen][flen]<<endl;//这就是总步数
89         showans(flen,tlen);
90     }
91     return 0;
92 }
https://vjudge.net/contest/382410#problem/B