(Invalid img)O,YEAH!!!写好了简单的方程,我们就可以开始想那讨厌的状态压缩了....

建议先搞出DP方程

再明白路径压缩……

var

a:array[-10..10050]of integer;

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

mm:array[0..102]of longint;

l,s,t,m,i,j,tt,ans:longint;

f1,f2:text;

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

begin

if a>b then min:=b

else min:=a;

end;

begin

readln(l);

readln(s,t,m);

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

if s=t then

begin

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

writeln(ans);

halt;

end;

mm[m+1]:=l;

for i:=1 to m do

for j:=i+1 to m do

if mm[i]>mm[j] then begin tt:=mm[i];mm[i]:=mm[j];mm[j]:=tt;end;

for i:=0 to m+1 do

if mm-mm[i]>90 then mm:=mm[i]+(mm-mm[i]) mod 90;

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

l:=mm[m+1];

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+a[i]);

ans:=maxint;

for i:=l to l+t do ans:=min(ans,f[i]);

writeln(ans);

end.

其实不是很难，动规方程很容易。只是要压缩。

不过一开始不知道它给的数据是无序的，没有排序，狂暴，特郁闷。真会坑人

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

路径压缩的Dp.

大于72的全部压成72.

方程就不说了吧,挺简单的.

激动啊………… 好不容易 过掉了……

我是用T对桥的长度进行压缩的，结果所有点全过！但是目前还没合理的解释，是数据问题还是用T压缩是可以的，如果用T压缩可以的话，有什么道理呢？请各位大牛帮助解答！

只要求出1--10里面任意两个数的最小公倍数，然后取最大的，可以证明当两石块之间的距离大于它的时候，那么大于它的部分的每一个点都可以通过这两个数的某一种组合跳到，所以当两个石块间的距离大于这个最小公倍数，那么就把它们的距离缩小到这个最小公倍数，应该就是这么个压缩原理吧？

一下引用http://www.nocow.cn/index.php/USACO/nuggets（自己懒得写了...)

我来证明一下。已知，不定方程 ax + by = c ( a , b > 0 且 c >= ab ) 存在 一组 整数解 ( x0 , y0 ) 求证，该不定方程存在一组非负整数解 ( xn , yn ) . 证明 : 由不定方程通解式得 : xn = x0 + b * t , yn = y0 - a * t ( t 是整数 ) 令 xn , yn >= 0 解出 - ( x0 / b ) = a * b 两边同除 a * b 得 : x0 / b - ( - y0 / a ) >= 1 所以 一定存在 整数 t 使得 - ( x0 / b )

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

too easy

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

排序 压缩 DP then AC

DP，说难不难，说易不易。。。

重点是状态压缩，我就是忽略了第一颗石子，CRACH了5个点

之后加了一句话。。。A掉

附状态压缩的做法：

if a[1] > 2520 then a[1]:=a[1] mod 2520;

if m > 1 then

for i:= 2 to m do

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

if l-a[m] > 2520 then l:=a[m]+(l-a[m]) mod 2520;

AC证书：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

128是什么错误啊？？？

编译通过...

├ 测试数据 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;

const

max=105;

var

a,a1:array[0..101] of longint;

b:array[0..100] of boolean;

c,d:array[0..10000] of longint;

l,s,t,m,ans,low,i,j,k,temp:longint;

flag:boolean;

procedure init;

begin

readln(l);

readln(s,t,m);

for i:=1 to m do

read(a[i]);

a[0]:=0;

a[m+1]:=l;

for i:=1 to m-1 do

for j:=i+1 to m do

if (a[i]>a[j]) then

begin

temp:=a[i];

a[i]:=a[j];

a[j]:=temp;

end;

end;

procedure work1;

begin

for i:=1 to m do

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

inc(ans);

end;

procedure work2;

begin

fillchar(b,sizeof(b),false);

b[0]:=true;

for i:=s to t do

begin

for j:=0 to 100 do

if (b[j]) then

begin

k:=1;

while (k*i+jc+d[i])) then

c[i]:=c+d[i];

ans:=max;

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

if (ans>c[i]) then

ans:=c[i];

end;

begin

init;

if (s=t) then

work1

else

work2;

writeln(ans);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

还是不明白为什么离散化要弄100or82甚至更小

我是统一弄成mod2520做的,也就是1-10的最小公倍数

DP部分很简单了

要注意最后一个点不一定能跳到..............我就向后面扩展了10个点,求最小值

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

超经典DP!!!一次AC!

状态压缩：

stone[0]=0;

stone[m+1]=l;

for (i=1;i90) {

tt=stone[i]-stone;

for (j=i;j

var

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

f:array[1..15000,1..2] of longint;

n,i,j,x:longint;

begin

readln(n);

for i:=1 to n do

readln(f,f);

for i:=1 to n do

begin

x:=0;

for j:=1 to n do

if (ij) and(f[j,1]

终于过了~~5555555~~

半天题解没看懂~~还是自己想的~~555555~~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

竟然要排序！邪恶的数据……

lovecd

var

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

f:array[1..15000,1..2] of longint;

n,i,j,kk:longint;

begin

readln(n);

for i:=1 to n do

readln(f,f);

for i:=1 to n do

begin

kk:=0;

for j:=1 to n do

　　if (ij) and(f[j,1]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

在rqnoj上交了4次，vijos上终于通过了，不过rqnoj上我的程序速度挺慢的，到vijos上0ms

不会……