J. 大乌龟冲呀！
Description
在杂志社工作的小鹏在休息日突然接到老板丢过来的文本编辑任务，要求将一串漏洞百出的文本A AA 编辑为小鹏认为合理的文本$B$，小鹏一次可以对一个字符进行插入、删除和替换操作，每种操作需要耗费的时间分别对应为x xx，y yy，$z 分 钟 ， 然 而 小 鹏 一 心 只 想 看 分钟，然而小鹏一心只想看分钟，然而小鹏一心只想看T$ 分钟后的英雄联盟S10 全球总决赛，亲眼见证最喜欢的大乌龟战队夺冠。问：小明是否可以准时观看比赛？若可以，请告诉小明完成工作后还有多久开始比赛，否则输出比赛已经开始了多久。
Input
AA
B BB
X XX Y YY Z ZZ T TT
Output
Yes （or No） 和一个整数（如果时间准时看比赛，请输出Yes 0）
Samples
Input [Copy](javascript:)
abc adc 5 3 2 2
Output
Yes 0
Hint
0<|A|,|B|<60000<|A|,|B|<6000
1<x,y,z<100001<x,y,z<10000
Source
2020年烟大校赛
题意：
给定两个字符串A,B,每次可以对一个字符进行插入、删除和替换操作，权值分别为x,y,z。问要将A变为B的最小权值。
思路：
编辑距离的板子题了，只是碰见好几次了都没想起来，而且这题DP状态还很巧妙。
我们设dp[i] [j]表示将A的前i个字符变为B的前j个字符需要的最小权值，这样dp[lena] [lenb]就是答案了。
再来考虑状态转移，有三种操作：插入、删除和替换。
插入操作：表示B的第j个字符是插入进去的，上一个状态就是dp[i] [j-1]，权值是x。
删除操作：表示A的第i个字符要删除，上一个状态是dp[i-1] [j]，权值是y。
替换操作：上一个状态就是dp[i-1] [j-1]，考虑a[i]和b[j]是否相等，如果相等的话，权值为0；否则，权值为z。
最后来看看初始化：
当i==0时，dp[i] [j] 表示A的前0个字符变为B的前j个字符的权值，因为A没字符，所以只能够由插入得到，权值就是x*j；
当j==0时，dp[i] [j] 表示A的前i个字符变为B的前0个字符的权值，因为B没字符，所以只能够由删除，权值就是y*i；
代码：
ll dp[6011][6011]; char a[6010],b[6010]; int main() { scanf("%s%s",a+1,b+1); ll lena=strlen(a+1),lenb=strlen(b+1); ll x=read(),y=read(),z=read(),t=read(); for(int i=0;i<=lenb;i++) dp[0][i]=i*x; for(int i=0;i<=lena;i++) dp[i][0]=i*y; for(int i=1;i<=lena;i++){ for(int j=1;j<=lenb;j++){ dp[i][j]=min(dp[i-1][j]+y,dp[i][j-1]+x); if(a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]); else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+z); } } if(dp[lena][lenb]<=t) printf("Yes 0\n"); else printf("No %lld\n",dp[lena][lenb]-t); return 0; }
