编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我在CENA上好几个超时。。。这题，比赛时看也不看就跳过的旷世难题！

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

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

=========咱自己学校的题，现在才把它做了=========

关键在于要知道同余定理，这样就能很自然的写多DP来了

f:前i个数到数字j的余数,要加的最少乘号。

b表示数字i到数字j的余数

f[k,s]:=min{f+1}

(i+1

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

啊 20次提交终于过了

多少辛酸往事 尽在不言中

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

莫非是rp好...

为什么看到好多人的用了好多时间...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

DP真是博大精深

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

program v1455;

var

ch:char;

r:array[1..1000,0..1000]of longint;

data:array[1..1000]of longint;

a:array[1..1000,0..50]of longint;

i,j,p,n,m,q:longint;

procedure work(p,q:longint);

var i:longint;

begin

r[p,q]:=(r[p,q-1]*10+data[q]) mod m;

end;

begin

while not eoln do

begin

inc(n);

read(ch);

data[n]:=ord(ch)-ord('0');

end;

readln;

readln(m);

for j:=1 to n do work(1,j);

for i:=1 to n do for j:=0 to m do a:=maxlongint;

for i:=1 to n do a[i,r[1,i]mod m]:=0;

for i:=1 to n do

for j:=0 to m-1 do

for p:=i+1 to n do if amaxlongint then

begin

if r=0 then work(i+1,p);

q:=j*rmod m;

if a[p,q]>a+1 then a[p,q]:=a+1;

end;

for i:=0 to m-1 do if a[n,i]maxlongint then break;

write(i,' ',a[n,i],' ');

for i:=m-1 downto 1 do if a[n,i]maxlongint then break;

writeln(i,' ',a[n,i]);

end.

本人动规好弱，交了４遍……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最开始交的程序多了个常数，结果一半数据TLE

我好菜 = =！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

haha

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

好险啊……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

貌似不快不慢的...

第一次预处理弄错了. 居然过了一半~···

回答楼上：把余数是0..m-1的都记录下来就无后效性了。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一遍Ac。总时间比楼上的都短一点。

弱弱地问一句，为什么可以用DP？

怎么确定它符合无后效性呢？

比如说，前L-1个数最小余数是5，乘以最后一个数3后，变成15，除以m=16余15

但是如果前L-1个数可以余数是7，乘以最后一个数3后，变成21，除以m=16余5

不就不是最优解了？

no.1 预处理

no.2 边界处理

no.3 进入DP

Fatal: Syntax error, "BEGIN" expected but "identifier CHR" found

Fatal: Compilation aborted

我真服了,什么错都能出来 为了此水题AC率猛降2%

以后坚决不用记事本了,我现在想骂人了,但是我的理智尚存,我\(%^%&\*%\*\)^#^$&*(**@)(&))(^&

45分的程序

var s:ansistring;

n:longint;

begin

readln(s);

read(n);

write(0,' ',1,' ',n-1,' ',1);

end.

虽然题目讲 :"会做乘积最大,做此题不会太难. 其实这是一中误导,因为在乘积最大那题中,我们用F表示从I到J可以得到的最大乘积,F[1,N]即为解.而此题中如果你也想用F表示从I到J的最小或最大余数,发现是有后效性的.

做这一类一般把余数做为一种状态而不是记录的解.具体的DP方案楼下已经很很多牛说过了,我就不再赘述.

其实当你做很多DP题时都会发现你第一次想出的方法是有后效性的,这时不要已经题目不是叫你用DP做,看题目给出的数据规模应该相信这一定是DP,换种思路,你或许能得到意想不到的收获..^_^

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

纪念一下

特别感谢cly

60分的同志门注意一下

提前处理的时候的复杂度（L*L）

总程序复杂度为（N*N*M）就能A了

虽然不是秒杀

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

动规