【t003】string

Time Limit: 1 second
Memory Limit: 50 MB

【问题描述】

设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。 如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为0。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。 请你写一个程序，求出字符串A、B的距离。

【输入】

共3行；
第一行为字符串A。
第二行为字符串B，A、B均由小写字母组成且长度均不超过2000，第三行为一个整数K，1≤K≤100，表示空格与其它字符的距离。

【输出】

包含1行,一个整数，表示要求的字符串A、B的距离。

【输入样例】

cmc
snmn
2

【输出样例1】

10

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t003

【题意】

【题解】

/*
    设f[i][j]表示A的子串A[1..i]的扩展串
    和B的子串B[1..J]的扩展串的距离;
    这里这两个扩展串的长度是一样的.
    则
    f[i][j] = min(f[i-1][j]+k,f[i][j-1]+k,f[i-1][j-1]+abs(A[i]-B[j]));
    分别对应了A在后面加上A[i],然后B在后面加上空格;
    B在后面加上了B[j],然后A在后面加上了空格;
    以及A和B分别在后面加上了A[i]以及B[j];
    边界条件
    f[0][i] = i*k,f[i][0] = i*k;
*/

【完整代码】

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 2100;

char A[N], B[N];
int k,la,lb,f[N][N];

void input_data()
{
    scanf("%s", A + 1),scanf("%s", B + 1);
    la = strlen(A + 1), lb = strlen(B + 1);
    rei(k);
}

void Dp()
{
    rep1(i, 1, la) f[i][0] = i*k;
    rep1(i, 1, lb) f[0][i] = i*k;
    rep1(i,1,la)
        rep1(j, 1, lb)
        {
            f[i][j] = min(f[i - 1][j] + k, f[i][j - 1] + k);
            f[i][j] = min(f[i - 1][j - 1] + abs(A[i] - B[j]), f[i][j]);
        }
}

void o()
{
    printf("%d
", f[la][lb]);
}

int main()
{
    //freopen("F:\rush.txt", "r", stdin);
    input_data();
    Dp();
    o();
    //printf("
%.2lf sec 
", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}