学步园

【题意】

n(n<=20)头牛进行自行车比赛

需要跑d(d<=100)圈

每头牛初始有e(e<=100)的体力

流程按整分钟划分

比赛的时候若以x圈每分钟的速度前进，则领头牛每分钟消耗x*x的体力，其余牛每分钟消耗x的体力

若牛的体力小于x，则牛掉队

可在每分钟调换领头牛

只要有一头牛跑完要求圈数则算完成，问最快跑完需要几分钟

【输入】

 一行n,e,d

【输出】

若能跑完则输出最小用时，否则输出0

最初的思路是用【以跑圈数】【领头牛体力】【剩余牛体力】【剩余牛数量】来表示状态

但是这个是四维的，应该会超，数组也开不下

之后发现实际上领头牛是一头用完掉队了再让剩余牛上，不会出现归队的情况

这样剩余牛的状态都是一样的，剩余牛以x圈每分钟的速度前进，则每分钟消耗x的体力，

反过来说跑y圈，剩余牛门则消耗y的体力

所以剩余牛的体力可以用e-【以跑圈数】算出，省下了一维

dp，用f[i][j][k]表示已经跑了i圈，领头牛有j的体力，除领头牛外剩余牛有k只所需的最小时间

初始状态为f[0][e][n-1]

然后用类似spfa的方式拓展状态求解

program poj1946;
var
  n,e,d,i,j,k,tot,ans:longint;
  f:array [0..101,0..101,0..21] of longint;
  dl:array [0..100001] of record
                           d,e,n:longint;
                         end;
begin
  read(n,e,d);
  fillchar(f,sizeof(f),63);
  if (e<d)or(n=0) then
    begin
      writeln(0);
      exit;
    end;
  f[0,e,n-1]:=0;
  tot:=1;
  dl[1].d:=0;
  dl[1].e:=e;
  dl[1].n:=n-1;
  ans:=maxlongint;
  i:=1;
  while i<=tot do
    begin
      if dl[i].d=d then
        if f[dl[i].d,dl[i].e,dl[i].n]<ans then
          ans:=f[dl[i].d,dl[i].e,dl[i].n];
      for j:=1 to trunc(e-dl[i].d) do
        begin
          if j*j<=dl[i].e then
            if f[dl[i].d+j,dl[i].e-j*j,dl[i].n]>f[dl[i].d,dl[i].e,dl[i].n]+1 then
              begin
                f[dl[i].d+j,dl[i].e-j*j,dl[i].n]:=f[dl[i].d,dl[i].e,dl[i].n]+1;
                inc(tot);
                dl[tot].d:=dl[i].d+j;
                dl[tot].e:=dl[i].e-j*j;
                dl[tot].n:=dl[i].n;
              end;
          if (dl[i].n>0)and(e-dl[i].d>=j*j) then
            if f[dl[i].d+j,e-dl[i].d-j*j,dl[i].n-1]>f[dl[i].d,dl[i].e,dl[i].n]+1 then
              begin
                f[dl[i].d+j,e-dl[i].d-j*j,dl[i].n-1]:=f[dl[i].d,dl[i].e,dl[i].n]+1;
                inc(tot);
                dl[tot].d:=dl[i].d+j;
                dl[tot].e:=e-dl[i].d-j*j;
                dl[tot].n:=dl[i].n-1;
              end;
        end;
      inc(i);
    end;
  writeln(ans);
end.