编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var n1,n2,k,i,j:longint;

st1,st2:ansistring;

f:array[0..2003,0..2003]of longint;

function min(x,y,z:longint):longint;

begin

if x>y then min:=y else min:=x;

if min>z then min:=z;

end;

begin

readln(st1);

n1:=length(st1);

readln(st2);

n2:=length(st2);

readln(k);

f[0,0]:=0;

for i:=1 to n1 do f:=f+k;

for i:=1 to n2 do f[0,i]:=f[0,i-1]+k;

for i:=1 to n1 do

for j:=1 to n2 do

f:=min(f+abs(ord(st1[i])-ord(st2[j])),

f+k,f+k);

writeln(f[n1,n2]);

end.

Flag 　　 Accepted

题号 　　P1680

类型(?) 　　动态规划

通过 　　96人

提交 　　144次

通过率 　　67%

难度 　　1

初值!!!!

f:=i*k;

f[0,j]:=j*k;

编译通过...

├ 测试数据 01：答案正确...ms

├ 测试数据 02：答案正确...ms

├ 测试数据 03：答案正确...ms

├ 测试数据 04：答案正确...ms

├ 测试数据 05：答案正确...ms

├ 测试数据 06：答案正确...ms

├ 测试数据 07：答案正确...41ms

├ 测试数据 08：答案正确...25ms

├ 测试数据 09：答案正确...103ms

├ 测试数据 10：答案正确...212ms

Accepted 有效得分：100 有效耗时：381ms

No. 94 AC!!

算法题解：

字符串A和B的扩展串最大长度是A和B的长度之和。如字符串A为“abcbd”，字符串B为“bbcd”，它们的长度分别是la=5、lb=4，则它们的扩展串长度最大值为LA+LB=9，即A的扩展串的5个字符分别对应B的扩展串中的5个空格，相应B的扩展串的4个字符对应A的扩展串中的4个空格。例如下面是两个字符串的长度为9的扩展串：

a□b c□b□d□

□b□□b□c□d

而A和B的最短扩展串长度为la与lb的较大者，下面是A和B的长度最短的扩展串：

a b cbd

b□bcd

因此，两个字符串的等长扩展串的数量是非常大的，寻找最佳“匹配”（对应位置字符距离和最小）的任务十分繁重，用穷举法无法忍受，何况本题字符串长度达到2000，巨大的数据规模，势必启发我们必须寻求更有效的方法：动态规划。

记为A串中A1到Ai的一个扩展串，为B串中B1到Bj的一个扩展串。这两个扩展串形成最佳匹配的条件是（1）长度一样；（2）对应位置字符距离之和最小。

首先分析扩展串与扩展串长度一样的构造方法。扩展串与扩展串可以从下列三种情况扩张成等长：

（1）与为两个等长的扩展串，则在后加一空格，加字符Bj；

（2）与为两个等长的扩展串，则在添加字符Ai，在后加一空格；

（3）与为两个等长的扩展串，则在后添加字符Ai，在后添加字符Bj。

其次，如何使扩展成等长的这两个扩展串为最佳匹配，即对应位置字符距离之和最小，其前提是上述三种扩展方法中，被扩展的三对等长的扩展串都应该是最佳匹配，以这三种扩展方法形成的等长扩展串(A1, A2, …, Ai>和也有三种不同情形，其中对应位置字符距离之和最小的是最佳匹配。

为了能量化上述的构造过程，引入记号g[i, j]为字符串A的子串A1, A2, …, Ai与字符串B的子串B1, B2, …, Bj的距离，也就是扩展串与扩展串是一个最佳匹配。则有下列状态转移方程：

g[i, j]=Min{g[i-1, j]+k, g[i, j-1]+k, g[i-1, j-1]+ c} 0≤i≤La 0≤j≤Lb

其中，k位字符与字符之间的距离； 为字符ai与字符bi的距离。

初始值：g[0, 0]=0 g[0, j]=j*k g[i, 0]=i*k

一次ac

设f为a串(1,i)子串与b串(1,j)字串的最小距离

f=i*k;

f[0,j]=j*k;

f=min{f,f,f+abs(ord(a[i])-ord(b[j]))};

Accepted 有效得分：100 有效耗时：49ms

遗憾 未秒杀 求ms牛解

上天啊，我有罪！！！原题加水题，我竟然看了题解才做出来！！！

话说这就是南京大学出的教材的习题的DP第一题。。。

注意边界：f[0,i]和f!!!

被昨天的模拟赛 搞的完全失败后

做这题能涨RP么？

好久没见到这么水的题了……

#include

using namespace std;

char a[2001],b[2001];

int k,f[2001][2001],n,m;

int main(void)

{

int i,j;

cin>>a>>b;

n=strlen(a);

m=strlen(b);

cin>>k;

for (i=1;i

水题....

74%的通过率...这题还不过可以回去搞文化课了

罕见的通过率72%的DP。。不过还是耗了半个小时- -。。残念了。。

显然两位只有3种情况：相对，相错（2种），故很容易想到状态转移方程：

f=min(min(f,f)+k,f+p)

i，j表示s1，s2的第i位和第j位，末状态显然是f[l1,l2]，因为末尾存在空格没有意义（如果你觉得有意义。。那么请重读小学一年级。。）

注意边界条件：f=k*i,f[0,i]=k*i。因为i前面还有i-1个字符此时也对着空，所以f:=f+k,又f[0,0]:=k，故f:=k*i。f[0,i]同理。

话说这题的样例很善良。。没有想到这个边界样例就会wa。。

话说我很想知道lx那位写了250行的大牛是怎样搞的。。话说我只有22行。。

方程好想...关键是预处理

f=k*i

f[0,j]=k*j

其实也是多想想就出来了

童鞋们注意ansistring。。。。。。。。

我居然交了两次。。。。。。

program vijos1680;

var f:array[0..2001,0..2001]of longint;

i,j,k:longint;

s1,s2:ansistring;

function min(a,b,c:longint):longint;

var t:longint;

begin

if a>b then t:=b else t:=a;

if t>c then exit(c) else exit(t);

end;

begin

readln(s1);

readln(S2);

readln(k);

for i:=1 to length(s1) do

f:=f+k;

for i:=1 to length(s2) do

f[0,i]:=f[0,i-1]+k;

for i:=1 to length(s1) do

for j:=1 to length(s2) do

f:=min(f+k,f+k,f+abs(ord(s1[i])-ord(s2[j])));

writeln(f[length(s1),length(s2)]);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：50ms

这什么状况？掉RP了......

注意ansistring 或者用char数组

不可能存在两个空的。。所以DP。。

maxthon

遭受模拟赛的打击后来涨信心的...

250行的程序

有效得分：100 有效耗时：749ms

纠结啊~~

第十个。赶上了。

占座= =

DP...

What is DP?