var

l,s,t,m,i,j,k:longint;

a,b,c:array[0..1000] of longint;

function f(i:longint):longint;

var

v,u,q,o:longint;

begin

if c[i]=-1

then begin

if i

[red]

路经压缩90即可ac

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一遍AC，高兴-ing

当s==t时要单独算，差点错了

经过若干次疯狂的存取非法后。。。

终于0MS AC了。

其实不需要把步长设为100，如果距离大于T,就把坐标修改一下直到距离为t就是了

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

路径压缩使用的数值可以算一下。

设对于特定的s和t,压缩使用的数值最小值为r.

则有以下算法：

若 (s-1)mod(t-s)为0,

则 r 为 (s-1)/(t-s)*s;

若 (s-1)mod(t-s)不为0,

则 r 为 ((s-1)/(t-s)+1)*s;其中(s-1)/(t-s)取除得的商。

若求得的r为0，则将r改为2.

这个公式可以通过写个程序穷举s,t，输出相应的状态然后寻找规律得到。

注意：s=t时，r=∞，即不能压缩，也即不能DP。

而 当 1

基于状态压缩的DP。

做了1年了，前前后后写了7、8套程序，今天终于AC了~~~~

首先，石头是需要排序的，没话说，我第一次就错在这上面（当然DP也不对）。

再者，关键是状态的压缩，因为当两个石头的距离过长的时候，青蛙大部分时间都用来蹦跳白地。即因为两石之间差距太大，青蛙不管跳S还是跳T都在白地上跳。作为与小动物和谐共处的我们自然不能看小小青蛙受到如此虐待，我们只去关注在靠近石子不远的地方青蛙的活动就可以了。所以把距离mod某个数以缩剪掉白地部分。这个某个数我不会证明怎么来取，我只知道mod100的话会RP的AC。

{这里一个实现技巧，把Stone[0]:=0;Stone[M+1(一)]:=BridgeLong，到时候把Stone[M+1(一)]再赋回BridgeLong可以同时缩减BridgeLong}

最后就是一些细节问题了，比如从0~S之间的点是无论任何也跳不到的（除非它在跳的途中做了次垂直落体运动），所以DP从S开始。而且最后需要从BridgeLong到BridgeLong+T中找最优解，因为题目允许跳过去。

最后后，总而言之，这其实是一道很简单的DP，不要被状态压缩的名头吓到。它与其它DP题目最大的区别在于代码长了不少。

var

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

i,j,k:longint;

l,m,s,t,pos,min:longint;

begin

fillchar(f,sizeof(f),0);

readln(l);

readln(s,t,m);

for i:=1 to m do

begin

read(pos);

f[pos]:=1;

end;

for i:= l downto 0 do

begin

min:=f;

for j:=t downto s do

if min>f then min:=f;

f[i]:=f[i]+min;

end;

writeln(f[0]);

end.

30分 程序

无语。我交了10次才过。算是有点收获，懂得了一点离散化。

1.朴素DP 20分

2.缩小L，temp:=(c[i]-c)div t,若temp>1 则大大缩小了L的长度。

c[i]为第i个石子的初始位置， 70分

3.瞄题解了，看别人直接判断c[i]-c>100就变100。好妙，因为最多只有100个点，加起来不会超过10000就可以用数组模拟了。 80分

4.可恶的是，居然还有s=t的情况需要特殊考虑。因为当此时，全程仅有一个路线，只能通过算c[i]是否在n*s的位置上来计算石子个数，不能用压缩。 100分。

看看时间，已经12点了。

感动阿，在无数次错误216以后……

其实是很sb的没有考虑要把l也缩短缩短……

没排序……郁闷了……

http://hi.baidu.com/%CB%D5%CC%DAsauterne/blog

特判s=t情况!

丫丫 一次AC啊

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

顺便纪念一下Flag 　　

题号 　　P1002

类型(?) 　　动态规划

通过 　　3500人

提交 　　17916次

通过率 　　20%

难度 　　3

第3500个过 嘢O(∩_∩)O哈！

其实这道题目以前看过 只不过没做 被数据吓到了 (ˇˍˇ）！！

今天下决心做了它

后来看了各位AC了的发言

然后知道怎么压缩路径

我是把两块石头大于100的 直接等于100

然后DP

.....

虽然不知道为什么

......

.........

..............

.........................

.................................................

话说，这叫不求甚解

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

提交6次,调试1小时,原来选择排序打错

#include

int s,t,m,x,p=0;

long f[100000]={0};

int r[120]={0};

long map[100000]={0};

int main()

{

long l,k;

int i,j,min;

scanf("%ld%d%d%d",&l,&s,&t,&m);

for(i=1;i

输入的数据是无序的啊.......

水题

缩点缩点...

据说可以称为离散化

然后DP

提交N次之后终于AC了。。

for i:=1 to m+1 写成for i:=1 to m WA了我6个点

总算AC了，但还是有很多不明白的，再做，AC率低，我也没办法了

为什么状态压缩的时候要mod 90？ s,t都不到10， 为什么 我 mod 11 会WA两个点？ mod 20 WA 一个点, mod 50 就AC了？？？

总结一下，这道号称史上最难DP的题我做了一晚上，发现也不是很难:

1.特殊情况 s=t时，DP有些点就无法处理(有些点无法到达，压缩后可能就到达了)

2.sort 题目没说有序，我们就要sort;(多少牛们死在这个上面了）

3.处理技巧 比如l:=a[m+1] 这样就不用每次都去减l了 还有就是当s=t时我们可以用a[i] mod m做，不用在f[i]上做 有时候换下思路效果会很好 NOIP2008第二题我就因为总想用火柴棍树去算可以拼成多少种数字，实在做不出来就cheat了30分，从而与省一失之交臂

努力！！！

program p1002;

const

maxl=4000;

maxm=100;

var

l,i,j,ans:longint;

s,t,m:byte;

stone:array[0..maxm+1] of longint;

b:array[1..maxl] of byte;

f:array[-10..maxl] of longint;

procedure swap(var a,b:longint);

var c:longint;

begin

　　c:=a;a:=b;b:=c;

end;

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

begin

　　if astone[j]

　　　　then swap(stone[i],stone[j]);

stone[0]:=0;stone[m+1]:=l;

for i:=1 to m+1 do

　　if stone[i]-stone>90

　　 then stone[i]:=stone+(stone[i]-stone) mod 90;

l:=stone[m+1];

fillchar(b,sizeof(b),0);

for i:=1 to m do

　　b[stone[i]]:=1;

for i:=-10 to 0 do

　　f[i]:=0;

for i:=1 to l+t do

　　f[i]:=maxint;

for i:=s to l+t do

　　for j:=s to t do

　　 f[i]:=min(f[i],f+b[i]);

ans:=maxint;

for i:=l to l+t do

　　ans:=min(ans,f[i]);

writeln(ans);

end.