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.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

AC了，庆祝！！！

program river;

var

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

a,b,f:array[-10..10000] of longint;

c:array[0..100000] of boolean;

procedure print;

begin

writeln(min);

halt;

end;

begin

readln(l);

readln(s,t,m);

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

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

fillchar(c,sizeof(c),0);

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

if s=t then begin

min:=0;

for i:=1 to m do

inc(min,ord(a[i] mod s=0));

print;

end;

for i:=1 to m-1 do

for j:=1 to m-i do

if a[j]>a[j+1] then begin a[0]:=a[j];a[j]:=a[j+1];a[j+1]:=a[0];end;

a[0]:=0;

for i:=1 to m do begin

if a[i]-a>=100

then b[i]:=b+100

else b[i]:=b+a[i]-a;

c[b[i]]:=true;

end;

for i:=1 to s-1 do f[i]:=maxlongint;

for i:=s to b[m]+t do begin

min:=maxlongint;

for j:=i-t to i-s do

if (f[j]

type arr=array[0..100000] of longint;

var a,f,stone,stone2:arr;

l,s,x,t,m,n,o,p,i,j,k,min:cardinal;

procedure deal;

var i:longint;

begin

stone[0]:=0;

stone[m+1]:=l;

for i:=1 to m+1 do

if stone[i]-stone>=100 then stone2[i]:=stone2+100

else stone2[i]:=stone2+stone[i]-stone;

end;

begin

readln(l);

readln(s,t,m);

for i:=1 to m do

read(stone[i]);

if s=t then begin

for i:=1 to m do

if stone[i] mod s=0 then inc(o);

writeln(o);

end

else begin

for i:=1 to m-1 do

for j:=1 to m-i do

if stone[j]>stone[j+1] then begin

stone[0]:=stone[j];

stone[j]:=stone[j+1];

stone[j+1]:=stone[0];

end;

Deal;

l:=stone2[m+1];

for i:=1 to m do

a[stone2[i]]:=1;

f[0]:=0;

for i:=1 to l+t do begin

f[i]:=maxlongint-1;

for j:=t downto s do

if i

var

l,i,j,k,smi,xxo,sma,m:longint;

a,b,f,ma:array[-100..1000000] of longint;

begin

assign(input,'river.in');

reset(input);

assign(output,'river.out');

rewrite(output);

readln(l);

readln(smi,sma,m);

for i:=1 to m do

read(a[i]);

for j:=1 to m do

for i:=1 to m-j do

if a[i]>a then begin

a[0]:=a[i];

a[i]:=a;

a:=a[0];

end;

if smasmi then begin

b[1]:=a[1];

a[m+1]:=l;

a[0]:=0;

for i:=1 to m+1 do

if a[i]-a>82 then b[i]:=b+82

else b[i]:=b+a[i]-a;

l:=b[m+1];

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

for i:=1 to m do

a[b[i]]:=1;

for i:=1 to l+sma do begin

f[i]:=maxlongint div 2;

for j:=smi to sma do begin

if i-jf+a[i] then f[i]:=a[i]+f;

end;

end;

end;

k:=maxlongint;

for i:=l to l+sma do

if f[i]

#include

#define MAXN 100

#define MAXS 100000

long stone[MAXN+1]={0};

int map[MAXS+1]={0};

long f[MAXS+1]={0};

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

void qsort(int l,int r){ /*排序石子*/

int i,j;

long x,t;

i=l;j=r;

x=stone[(i+j)/2];

do{

for(;stone[i]x;j--);

if(i

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

这什么数组......

编译通过...

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

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

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

├ 测试数据 04：运行时错误...| 错误号: 128 |

├ 测试数据 05：运行时错误...| 错误号: 128 |

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

├ 测试数据 07：运行时错误...| 错误号: 128 |

├ 测试数据 08：运行时错误...| 错误号: 128 |

├ 测试数据 09：运行时错误...| 错误号: 128 |

├ 测试数据 10：运行时错误...| 错误号: 128 |

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

Unaccepted 有效得分：40 有效耗时：0ms

编译通过...

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

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

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

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

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

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

├ 测试数据 07：运行时错误...| 错误号: 128 |

├ 测试数据 08：运行时错误...| 错误号: 128 |

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

├ 测试数据 10：运行时错误...| 错误号: 128 |

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

Unaccepted 有效得分：70 有效耗时：232ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

郁闷 。。。。 数组从 1..100000 一直开到了 1..1000000 才过

var

a,b,f:array[0..10000]of longint;

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

procedure qsort(l,r:longint);

var

t,i,j,mid:longint;

begin

i:=l;j:=r;

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

repeat

while b[i]mid do dec(j);

if ij;

if il then qsort(l,j);

end;

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

begin

if a>b then min:=b

else min:=a;

end;

begin

read(n);

read(s,t,m);

j:=0;

for i:=1 to m do

read(b[i]);

qsort(1,m);

j:=b[1];

if b[1]>t then

b[1]:=b[1] mod t+t;

a[b[1]]:=1;

for i:=2 to m do

begin

j1:=b[i];

if b[i]-t>j then

begin

l:=(b[i]-j)mod t+t;

b[i]:=b+l;

end

else b[i]:=b+(b[i]-j);

j:=j1;

a[b[i]]:=1;

end;

if n-k>t then

n:=b[m]+t+(n-k)mod t

else n:=b[m]+(n-k);

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

f[i]:=100000;

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

for j:=s to t do

if i-j>=0 then

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

j:=maxlongint;

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

if f[i]

Program P1002;

var

h:array[0..101] of longint;

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

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

n,s,t,m,min,i:longint;

procedure init;

var

i,j,d,k,min:longint;

begin

readln(n);

readln(s,t,m);

fillchar(h,sizeof(h),0);

for i:=1 to m do

read(h[i]);

for i:=1 to m-1 do

for j:=i+1 to m do

if h[i]>h[j] then

begin

d:=h[i];

h[i]:=h[j];

h[j]:=d;

end;

if s=t then

begin

min:=0;

for i:=1 to m do

if h[i] mod s=0 then

inc(min);

writeln(min);halt;

end;

inc(m);h[m]:=n+1;h[0]:=-1;

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

fillchar(a,sizeof(s),false);

for i:=1 to m do

if h[i]>h+91 then

begin

d:=h[i]-h-91;

dec(n,d);

for j:=i to m do

h[j]:=h[j]-d;

end;

for i:=1 to n-1 do

f[i]:=101;

for i:=1 to m do

a[h[i]]:=1;

end;

procedure main;

var

i,j,min:longint;

begin

for i:=s to n do

begin

min:=101;

for j:=i-t to i-s do

if min>f[j] then

min:=f[j];

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

end;

min:=101;

for i:=n-t to n do

if min>f[i] then

min:=f[i];

writeln(min);

end;

begin

assign(input,'in.txt');

reset(input);

assign(output,'out.txt');

rewrite(output);

init;

main;

close(input);

close(output);

end.

好题啊，估计考场时遇到也就最多30分了。

program river;

type stack=record

data:array[1..10000]of integer;t:integer;

end;

var np,tmp,ts,s,t,i,L:integer;

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

path:stack;

ans:array[1..10000]of integer;

anst:integer;

procedure addin;

var i:integer;

begin

inc(anst);

for i:=1 to path.t do if b[path.data[i]] then inc(ans[anst]);

end;

procedure qsort(l,r:integer);

var tmp,i,j,mid:integer;

begin

i:=l;j:=r;mid:=ans[(i+j) div 2];

repeat

while ans[i]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var l,i,j,k:longint;

s,t,m:longint;

u,v:longint;

a:array[1..105]of longint;

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

min:integer;

tf:boolean;

function flag(k:longint):boolean;

var i:longint;

begin

flag:=false;

for i:=1 to m do

if a[i]=k then begin

flag:=true;

break;

end;

end;

begin

readln(l);

readln(s,t,m);

for i:=1 to m do

read(a[i]);

readln;

for i:=1 to m-1 do

for j:=i+1 to m do

if a[i]>a[j] then

begin

k:=a[i];a[i]:=a[j];a[j]:=k;

end;

if s=t then begin

min:=0;

for i:=1 to m do

if a[i] mod s=0 then

inc(min);

writeln(min);

halt;

end;

u:=0;i:=1;v:=a[i];

repeat

if v-u>100 then begin

a[i]:=u+100;

for j:=i+1 to m do

dec(a[j],v-u-100);

dec(l,v-u-100);

end;

inc(i);

u:=a;

v:=a[i];

if i=m+1 then v:=l;

until i=m+2;

fillchar(f,sizeof(f),$7f);

f[0]:=0;

for i:=s to l+50 do

for j:=i-t to i-s do

if j>=0 then

begin

tf:=flag(i);

if tf then

if f[j]+1

错第三个点的同志注意S=T

if v>=s(s+1) then

v可以到达

if v>=9*10 then

任何都可以到达

所以90压缩

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

哦，过了。。。。。。

...

考虑使用矩阵乘法（当然观察上面式子可以直接发现一堆转移不用做，直接压缩即可）

对于两个石头之间用矩阵乘法转移掉，然后到了有石头的那个地方，人工矩阵乘法即可。O（log l*(t-s)^3），是可以接受的。

怎么没听明白

考虑普通的状态转移方程：

d(i)=min(d(i+k)+1); s

var

a,c:array[1..1000]of qword; b:array[1..1000]of boolean;

i,j,k,s,t,m,l,sum,good:integer;

begin

readln(l);

readln(s,t,m);

for i:=1 to m do begin

read(a[i]);

b[a[i]]:=true;

end;

i:=1;

while i

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.