CSU-1835 Pry Sequence Transformation(DP)
1835: Pry Sequence Transformation
Time Limit: 2 Sec Memory Limit: 128 Mb Submitted: 90 Solved: 22Description
Having solved the edit distance problem years ago, the head of Pry oil has a plan to streamline their formula library. A pry sequence, used to describe a Pry formula, is a sequence of lower-case letters (a through z). Such a sequence is a closely guarded secret and is managed by a computer program written by Pure Evil.
To record a new pry sequence, you have to start with an existing pry sequence and make edits. Pure Evil charges money for every alteration made. Each letter is priced differently:
val('a') == 1, val('b')==2, val('c')==3,…, val('z')==26.
Let A = a1a2...an (1 ≤ n ≤ 20,000) be an existing pry sequence, and B = b1b2...bm (1 ≤ m ≤ 20,000) be a new sequence to be recorded. You can:
·Insert one symbol into any position: inserting a symbol x incurs a cost of 1 + val(x)/100
·Delete one symbol from any position: deleting a symbol y incurs a cost of 1.
·Replace one symbol at any position: replacing a symbol y for a symbol x incurs a cost of [val(x) + val(y)]/10
For example: for a total cost of 3.21, you can turn 'ary' into 'tray' by (1) inserting 't' yielding 'tary' (cost: 1.2); (2) deleting 'a' yielding 'try' (cost: 1); and (3) inserting 'a' yielding 'tray' (cost: 1.01). However, you can do better. For a total cost of 3.11, you could instead (1) replace 'a' by 't' yielding 'try' (cost: 2.1); and (2) insert 'a' yielding 'tray' (cost: 1.01).
YOUR TASK: For a given pair of A and B, you will determine the cheapest cost to record B starting from A in Pure Evil's program. The head of Pry oil doesn't want to record any sequence that Pure Evil charges strictly more than K (0 ≤ K ≤ 100). For sequences that exceed the budget, you will output "TOSS" instead.
Input
The first line contains the number of test cases 1 ≤ T ≤ 20. Following that, there will be T sets of test cases, each containing three lines formatted as follows:
·The first line contains a single number K.
·The second line contains the pry sequence A (presented consecutively without any spaces or puncutation marks in between)
·The third line contains the pry sequence B (presented consecutively without any spaces or puncutation marks in between)
Output
You are to produce T lines. The i-th line contains the answer for i-th test case, reporting a single number that indicates the cost (with exactly 4 digits of accuracy) to make the pry sequence B from the given pry sequence A. If the cost exceeds the budget K, output the word “TOSS”. Note: Use printf(“%.4f”) available in both C/C++ and Java to correctly format the output.
Sample Input
3 4 ary tray 5 llllammpptp llllammpppt 3 bcabcabcabcabcabca abcbacabcabacbcabc
Sample Output
3.1100 2.1600 TOSS
加长版编辑距离（很简单，然而想了半天没想到怎么优化）
2个字符串长度|s|<=20000，每个字符的价值val(ch)=ch-'a'+13种操作的费用分别为：①插入：1+val(ch)*0.01;②删除：1；③替换：(val(ch1)+val(ch2))*0.1
要求总费用不能超过K(K<=100),输出最小费用
考虑到长度是2e4，因此不能用N*M的时间和空间复杂度
空间复杂度很好解决，可以使用滚动数组，空间复杂度O(N)
时间复杂度：因为费用不能超过K，那么如果当前2个字符串长度之差超过K一定是不行的，因此dp时第二维j∈[max(1,i-K-1),min(M,i+K+1)]
这样时间复杂度就可以变成O(N*K)
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
const int MX = 2e4 + 5;
char S[MX],T[MX];
double dp[2][MX];
int val(char c){return c-'a'+1;}
double INS(char c){return 1+val(c)*0.01;}
double REP(char c1,char c2){return c1==c2?0:(val(c1)+val(c2))*0.1;}
int main(){
int cas;
int k;
//freopen("in.txt","r",stdin);
scanf("%d",&cas);
while(cas--){
scanf("%d",&k);
scanf("%s%s",S+1,T+1);
int n=strlen(S+1),m=strlen(T+1);
dp[0][0]=0;
for(int i=1;i<=k;i++) dp[0][i]=dp[0][i-1]+INS(T[i]);
int cur,pre;
for(int i=1;i<=n;i++){
cur=i%2;
pre=cur^1;
dp[cur][0]=i;
int mx=min(m,i+k+1);
for(int j=max(1,i-k-1);j<=mx;j++){
dp[cur][j]=dp[pre][j-1]+REP(S[i],T[j]);
if(abs(i-j)<=k) dp[cur][j]=min(dp[cur][j],dp[pre][j]+1);
if(abs(j-i)<=k) dp[cur][j]=min(dp[cur][j],dp[cur][j-1]+INS(T[j]));
}
}
if(dp[cur][m]>k) printf("TOSS\n");
else printf("%.4f\n",dp[cur][m]);
}
return 0;
}