program p1002;

var

s,t,m,min,w:integer;

l,t1,i,j:longint;

f:array[0..10000] of integer;

a:array[0..10000] of boolean;

c:array[0..100] of longint;

begin

readln(l);

readln(s,t,m);

fillchar(a,sizeof(a),0);

for i:=1 to m do read(c[i]);

for i:=1 to m-1 do

for j:=i+1 to m do

if c[i]>c[j] then

begin

t1:=c[i];

c[i]:=c[j];

c[j]:=t1;

end;

if s=t then

begin

for i:=1 to m do

if (c[i] mod s=0) then inc(min);

writeln(min);

halt;

end;

l:=c[m];

t1:=0;

for i:=1 to m do

begin

if c[i]-c>=72 then

begin

a[t1+72]:=true;

inc(t1,72);

dec(l,c[i]-c-72);

end

else

begin

a[t1+c[i]-c]:=true;

inc(t1,c[i]-c);

end;

end;

for i:=1 to l+t do f[i]:=100;

f[0]:=0;

for i:=s to l+t-1 do

for j:=s to t do

begin

if a[i] then w:=1 else w:=0;

if i-j>=0 then

if f[i]>f+w then

f[i]:=f+w;

end;

min:=100;

for i:=l to l+t-1 do

if min>f[i] then min:=f[i];

writeln(min);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program river;

var l,s,t,m,a,b,c,g,h:longint;

x,y:array[0..100000] of longint;

p:array[1..1000000000] of boolean;

procedure init;

begin

readln(l);

readln(s,t,m);

for a:=1 to m do

begin

read(y[a]);

end;

end;

procedure qsort(l,r:longint);

var i,j,mid,n:longint;

begin

i:=l;

j:=r;

mid:=y[(i+j) div 2];

repeat

while (i

本题考的就是状态压缩！DP不是太难

研究了N久！在网上看了个程序！觉得他的压缩方法很好！

以每个石头阶段，只记录石头前面能一步跳到石头的格子~

由前一块石头的状态推出下个石头的状态，之前必须判断能否到达

判断方法：

function can(v:longint):boolean;

begin

if v=s*(s-1) then exit(true) else

exit(b[v]);

end;

说明：只要距离满足v>=s*(s-1)就可以由S和S+1的任意倍数相加获得

详细题解和代码说明可以到我的博客看看

www.onlygod.cn

if s=t then

each(a[i])

if a[i] mod s =0 then ans

扩大步长

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

直接压路径，不用压的很小，能过就行了-_-||| 注意排序和S=T.

var

f,b:array[0..260000]of integer;

a:array[0..2500]of longint;

l,s,t,m,i,j,w:longint; ch:char;

begin

read(l,s,t,m);

for i:=1 to m do

read(a[i]);

w:=0;

if s=t then begin

for i:=1 to m do

if a[i] mod s=0 then inc(w);

write(w);

exit;

end;

for i:=1 to m do

for j:=i to m do

if a[i]>a[j] then begin w:=a[i];a[i]:=a[j];a[j]:=w;end;

for i:=1 to m do

if a[i]-a>2520 then

begin w:=a[i]-a-2520;

for j:=i to m do

a[j]:=a[j]-w;

end;

for i:=1 to m do b[a[i]]:=1;

l:=a[m]+10;

for i:=1 to l do

begin f[i]:=100;

for j:=s to t do

if (i-j>=0)and(f[i]>f+b[i]) then f[i]:=f+b[i];

end;

write(f[l]);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

先排序（nlogn），再压缩路径（m），最后dp。

注意单独处理s=t的情况

即：

procedure specialize;

begin

ans:=0;

for i:=1 to m do if od[i] mod t=0 then inc(ans);

writeln(ans);

halt;

end;

压缩没压好，WA了NN次啊……

216 存取非法

为什么会有这样的提示？

必须使用压缩吗？

数组范围最大是多少？可以超过10^9吗？

压缩了。状态转移方程写错了。大牛讲一下

我压缩了，DP了，特判了，可还有两个点超时！！！

无语啊 数据居然是无序的

大家小心啊

突然发现这么多人写题解

作为此号AC的第一道题，居然不是一次AC

其实s=t的时候是可以dp的，完全没有问题

但s=t与路径压缩相矛盾了，所以要单独处理

就是说s=t时不能进行路径压缩，就直接mod求解就行了

http://blog.sina.com.cn/s/blog_4a443fd701000aqj.html

这个题解很详细。

做了一天才明白

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

晕哦，没考虑s＝t，浪费我那么多时间，总算ac

var

var

l,s,t,i,j,n:longint;

temp,min:longint;

a:array[0..100] of longint;

f:array[0..253000] of longint;

begin

read(l);

read(s,t,n);

for i:=1 to n do

read(a[i]);

for i:=2 to n do

for j:=1 to i-1 do

if a[i]2520 then

a[i]:=a+(a[i]-a) mod 2520;

for i:=1 to n do

f[a[i]]:=1;

for i:=1 to s-1 do

f[i]:=maxlongint-100;

if l-a[n]>2520 then

l:=a[n]+(l-a[n]) mod 2520;

for i:=s to l do

begin

min:=maxlongint;

for j:=s to t do

if f

太不仔细了，

开始既没有考虑数据无序，

也没有考虑S=T这种特殊情况，

结果都没全过。

要是2005年该我考就挂了...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

总算AC了

做了N年了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

终于过了！好高兴啊！

这题只需注意状态压缩 和s=t时的情况就行了

10的9次方大的数据怎么开呃?开不开..- -\