跳舞毯[XDU1005]

Problem 1005 - 跳舞毯

Time Limit: 2000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 308  Accepted: 108  Special Judge: No

Description

　　zyf不小心得了一种怪病，为了维持一天的精力他必须不停跳动。于是他买了一条跳舞毯，每天跳上几小时。众所周知，跳舞毯是给定一个序列，让你在指定时间踏指定的按钮，但zyf似乎不怎么擅长，为此他写了个外挂，以修改它的输入序列，得到满分！
　　这个外挂的厉害之处在于它能等到zyf跳完、输入序列后再进行修改，修改的方式有三种，在任意位置插入、删除或替换一个指令，每次插入需要a时间，删除需要b时间，替换需要c时间，现在zyf想用最短时间去修改他输入的序列得到满分（即与给定序列一样），但这显然已经超过了当前外挂的能力范围，于是只好求助于你，给这外挂写个补丁。

Input

　　输入包含多组数据，EOF结束。
　　每组数据包括三行，第一行包含三个整数a，b，c（0<a,b,c<=100)，如上文描述，第二行是跳舞毯给定的序列，第三行是zyf跳完、输入的序列，两者的长度都不大于1000，只包含大小写字母。

Output

　　每组数据输出一行，最少修改时间。

Sample Input

1 2 3
LDDD
DDDR
7 1 3
LDDR
LZRZDD

Sample Output

3
8

Hint

 

Source

2010.04内部测试赛（Author: Qinz）

水水的动归.第一次提交竟然没AC,把我吓尿了,后来发现把语言改成C++就过了,弱菜不知为什么.

#include<stdio.h>
#include<string.h>
int f[1010][1010];
char s1[1010],s2[1010];
int main()
{
    int a,b,c;
    while (scanf("%d%d%d",&a,&b,&c)!=EOF)
    {
        scanf("%s%s",&s2[1],&s1[1]);
        int len1=strlen(&s1[1]),len2=strlen(&s2[1]),i,j;
        memset(f,0,sizeof(f));
        for (i=0;i<=len1;i++)
            for (j=0;j<=len2;j++)
            {
                if (i==0 && j==0) continue;
                if (i==0)
                {
                    f[i][j]=j*a;
                    continue;
                }
                if (j==0)
                {
                    f[i][j]=i*b;
                    continue;
                }
                int tmp=1000000;
                if (f[i][j-1]+a<tmp) tmp=f[i][j-1]+a;
                if (f[i-1][j]+b<tmp) tmp=f[i-1][j]+b;
                if (s1[i]==s2[j])
                {
                    if (f[i-1][j-1]<tmp) tmp=f[i-1][j-1];
                }
                else
                {
                    if (f[i-1][j-1]+c<tmp) tmp=f[i-1][j-1]+c;
                }
                f[i][j]=tmp;
            }
        printf("%d
",f[len1][len2]);
    }
    return 0;
}