p1002.pas

来自「www.vijos.cn上一些习题的参考源码」· PAS 代码 · 共 90 行

var
  l,swap,u:dword;
  v:longint;
  s,t,n,m,i,j,sn,re,p,rn:byte;
  stone:array[1..101]of dword;
  dp:array[0..9]of byte;
//------------------------------------------------------------------------------
function min (a,b:byte):byte;
begin
  if a>b then
    exit(b)
  else
    exit(a);
end;
//------------------------------------------------------------------------------
begin
  readln(l);
  readln(s,t,m);
  for i:=1 to m do
    read(stone[i]);
  readln;
  for i:=1 to m-1 do
    for j:=i+1 to m do
      if stone[i]>stone[j] then
      begin
        swap:=stone[i];
        stone[i]:=stone[j];
        stone[j]:=swap;
      end;
  {stone[m+1]:=l;}
  n:=m; while(stone[n]>L) do dec(n);
  stone[n+1]:=l;

  fillchar(dp,sizeof(dp),100);
  dp[0]:=0;
  sn:=1;
  u:=1;
  rn:=0;
  while u<=l do
  begin
    i:=u mod t;
    p:=100;
    for v:=u-s downto u-t do
    begin
      j:=(v+t) mod t;
      if u<stone[sn] then
        p:=min(p,dp[j])
      else
        p:=min(p,dp[j]+1);
    end;

    if u=stone[sn] then inc(sn);

    if dp[i]=p then
      inc(rn)
    else
    begin
      rn:=0;
      dp[i]:=p;
    end;
    inc(u);
    if (rn>=t) and (u<stone[sn]) then
    begin
      {u:=(stone[sn]-u) div t*t+u;}
      u:=stone[sn]-t;
      rn:=0;
    end;
  end;
  re:=100;
  {dec(dp[l mod t]);}
  for i:=0 to t-1 do
    re:=min(re,dp[i]);
  writeln(re);

end.


{
动态规划
这道题的方程很好想，设dp[i]表示到i点最少碰到的石子数
dp[i]=dp[i-k]+s[i](s<=k<=t)，i处是石头则s[i]=1，否则=0。
但题目的规模是109，我们要解决两个问题，一是空间问题，二是时间问题。

空间问题：我们发现k的值最大只有10，所以可以用滚动数组，问题解决。
时间问题：朴素的做法是O(lt)的肯定要超时，但我们发现l最大109，m最大只有100，也就是说，在大多数情况下，两个石子的距离是相当大的，而动态规划却在这个相当大的距离上耗费太多的时间，算法的瓶颈就在这里。
不知道大家有没有看过星战，两个距离非常大的地方可以通过超时空来瞬间到达，这是个很好的思路。
顺着这个思路，我们设想一下，在这个距离内没有石子，意味着dp不会增加，只能不断调用之前的值。这时如果走了一圈发现没有任何变化，那么再走一圈呢？肯定依然没有变化，所以这时就可以"超时空"到下一个石头附近。
我们设rn记录重复次数，如果这个次数>=t，就是循环了一圈，这时直接到下一个石头附近，算法的复杂度是O(mt)，问题解决。
}