编辑距离问题
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：
(1)删除一个字符；
(2)插入一个字符；
(3)将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。
试编写程序，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。
Sol
设$f[i][j]$为字符串A前i位转换为字符串B前j位的编辑距离。
则有以下递推式：
$$f(i,j)=
\begin{cases}
f(i-1)(j-1)+1 & \text{a(i) != b(j)} \\
f(i-1)(j-1) & \text{a(i) == b(j)} \\
f(i)(j-1)+1 \\
f(i-1)(j)+1
\end{cases}
$$
时间复杂度：$O(n^{2})$
Description
Farmer John is building a nicely-landscaped garden, and needs to move a large amount of dirt in the process.
The garden consists of a sequence of $N$ flowerbeds ($1≤N≤100,000$), where flowerbed $i$ initially contains $A_i$ units of dirt. Farmer John would like to re-landscape the garden so that each flowerbed $i$ instead contains $B_i$ units of dirt. The $A_i$’s and $B_i$’s are all integers in the range $0…10$.
To landscape the garden, Farmer John has several options: he can purchase one unit of dirt and place it in a flowerbed of his choice for $X$ units of money. He can remove one unit of dirt from a flowerbed of his choice and have it shipped away for $Y$ units of money. He can also transport one unit of dirt from flowerbed $i$ to flowerbed $j$ at a cost of $Z$ times $|i−j|$. Please compute the minimum total cost for Farmer John to complete his landscaping project.
INPUT FORMAT (file landscape.in):
The first line of input contains $N$, $X$, $Y$, and $Z$ ($0≤X,Y≤108;0≤Z≤1000$). Line $i+1$ contains the integers $A_i$ and $B_i$.
OUTPUT FORMAT (file landscape.out):
Please print the minimum total cost FJ needs to spend on landscaping.
SAMPLE INPUT:
1 | 4 100 200 1 |
SAMPLE OUTPUT:
210
Sol
$O((NK)^{2})$
当 $N≤100$ 时，这道题可以转化为求编辑距离。复杂度$O((NK)^{2})$
We transform each landscape pattern into an array of length at most 1000 by listing out the locations of the individual units of dirt in the landscape in order. For example, if we have a landscape with heights 3,1,4,1, we would transform this into the sequence 0,0,0,1,2,2,2,2,3 (e.g., there are 4 units of dirt at position 2). Our problem now reduces to something very close to the computation of the “edit distance” between two sequences, which is a classical dynamic programming problem. Our goal is to transform one landscape sequence into another at minimum cost given three possible operations: insertion of a new character (at cost X), deletion of a character (at cost Y), or modification of a character (at cost Z times the magnitude of the change). This can be accomplished in O(N^2) time (where N=1000) using dynamic programming, as shown below. Each subproblem C[i][j] we solve along the way represents the minimum cost of transforming just the first i characters of the source sequence into just the first j characters of the target sequence.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#include <stdio.h>
#define INF 2000000000
#define MIN(x,y) ((x)<(y) ? (x) : (y))
#define ABS(x) ((x) > 0 ? (x) : -(x))
int A[1001], B[1001], nA, nB;
int C[1001][1001], X, Y, Z;
int main(void)
{
int i, j, n;
freopen ("landscape.in", "r", stdin);
freopen ("landscape.out", "w", stdout);
scanf ("%d %d %d %d", &n, &X, &Y, &Z);
for (i=0; i<n; i++) {
scanf ("%d", &j); while (j>0) { A[++nA] = i; j--; }
scanf ("%d", &j); while (j>0) { B[++nB] = i; j--; }
}
for (j=0; j<=nB; j++) C[0][j] = j*X;
for (i=0; i<=nA; i++) C[i][0] = i*Y;
for (i=1; i<=nA; i++)
for (j=1; j<=nB; j++) {
C[i][j] = INF;
C[i][j] = MIN(C[i][j], C[i][j-1] + X);
C[i][j] = MIN(C[i][j], C[i-1][j] + Y);
C[i][j] = MIN(C[i][j], C[i-1][j-1] + Z * ABS(A[i]-B[j]));
}
printf ("%d\n", C[nA][nB]);
return 0;
}
$O(NK)$
暂未看懂。。
英文题解