╭┐┌──╯┌╮─┬─┐

┌┼│││　╭┼　│　　

　││││　　│　│　　

　││││　╭┤─┼─┘

└┼│││　　│　│　　

└╯┘└╰┘└╯─┴─╯

抓狂

同个程序

第6次提交

终于过了

囧楼上的鄙视。。。

设f表示从i开始长为j的串需要添加的个数

若s[i]=s则f=f

否则f=min(f,f)

由于f只与j-1及j-2的情况有关，采用滚动数组，空间优化到O(n)

---|---|---|-以上是前面AC的大牛的题解---|---|---|---|---|---|-

或者将原字符串逆序，再求它们的LCS，f表示a[1..i]与b[1..j]的匹配个数

若a[i]=b[j]则f:=f+1

否则f=max(f,f)

利用滚动数组空间可以优化至O(n)

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一次AC。。。PUPPY无敌！

用两个数组c1[5001]c2[5001]滚动记录最长子序列大小就没有问题了。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

膜拜用时3位数以内的大牛们

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

├ 测试数据 14：答案错误...　

├ 标准行输出 1

　├ 错误行输出 2

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

LCS经典

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

纪念下 第 701 个···

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Lora Temper交了三次才过

无数次的TLE.坚定不移的交.一个百分点换来的

iloahz好牛。。0ms

Lora Temper有问题

我前两次相同的程序提交，都错了另一次0 ms就过的点，TLE

第三次提交才过， 无语

Longint+滚动数组：

编译通过...

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

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

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

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

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

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

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

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

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

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

├ 测试数据 11：运行超时...

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

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

├ 测试数据 14：运行超时...

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

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

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

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

Unaccepted 有效得分：94 有效耗时：3353ms

Integer+不滚动数组：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

差距咋就这么大呢？囧ing...

最最郁闷的，数据14，0ms和超时的差距啊！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

超短程序……时间没去优化。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我直接用的LONGINT

开5000*5000会超，但我用了一个优化

用2个5000的一维数组来回存储

空间复杂度轻松解决。

看LORA TEMPER被卡就立刻点了提交，结果TIGER把我这题弄过了

ansistring.

果然好慢.

不过还是AC了.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

还是字符数组效率高

注意：开DP时要使用integer而不能使用longint，否则会内存逸出！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

var

sa,sb:ansistring;

i,j,l,n:longint;

f:array[0..5000,0..5000]of integer;

function max(a,b:longint):longint;

begin

if a>b then exit(a);

exit(b);

end;

begin

readln(l);

readln(sa);

for i:=l downto 1 do

sb:=sb+sa[i];

for i:=1 to l do

for j:=1 to l do

begin

if sa[i]=sb[j] then f:=f+1

else f:=max(f,f);

end;

writeln(l-f[l,l]);

end.

///

晚了一部,

我是第667个...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Flag 　　 Accepted

题号 　　P1327

类型(?) 　　动态规划

通过 　　666人

提交 　　2269次

通过率 　　29%

难度 　　2

O(∩_∩)O哈哈~，我是第666个AC的！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

├ 测试数据 16：运行超时...

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

换了一个超时

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：运行超时...

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：97 有效耗时：869ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

├ 测试数据 07：运行超时...

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

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

├ 测试数据 10：运行超时...

├ 测试数据 11：运行超时...

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

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

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

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

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

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

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

Unaccepted 有效得分：84 有效耗时：969ms

一样的程序…………………………………………

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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