题解 P1329 【数列】

夏色祭 · 2017-09-07 17:13:44 · 题解

没人发题解

蒟蒻的我没A之前这题难度还是尚无评定，然后蒟蒻的我果断交了普及(NOI)+的难度，毕竟这题还是有点难(shui)的

华丽丽的分割线---------------------------------------------------------------------------------------------------------

我们用f[i,j,k]表示第i个数为j总和为k的方案数有多少

显然，当第i个数能为j的话，根据题意，前一个数（也就是i-1个数）肯定是j-1或者j+1，而1~i-1的总合肯定是k-j

那么：f[i,j,k]:=f[i-1,j-1,k-j]+f[i-1,j+1,k-j]

最终方案数就是对f[n,i,s]进行求和就行了

还有一点，f数组定三维可能会超内存，可以用个滚动数组，本来三维的数组就变成了两个二维的数组了。。

然后就是路径。。

用另外一个数组zz[i,j,k,1]表示f[i-1,j-1,k-j]是否存在方案，存在即保存j-1，意为可以从j-1得到当前的状态，zz[i,j,k,2]保存f[i-1,j+1,k-j]是否存在方案。

最后，用递归输出就行了

（我的代码大概是当前所有AC代码里跑得最慢的了。。。）

献上没有66666a代码丑陋的code:

var
  zz:array[0..100,-100..100,-2000..2000,1..2]of shortint;
  f,ff:array[-100..100,-5000..5000]of int64;
  tt:array[0..100]of longint;
  n,m,i,j,k,sum:longint;
  ans:int64;
procedure print(i,j,k:longint);
var
  t:longint;
begin
 // writeln(i,' ',j,' ',k);
  if k+(j*2+(n-i+1))*(n-i) div 2<m then exit;//剪枝，没有这句60
 // if k-(j*2+(n-i+1))*(n-i) div 2>m then exit;
  tt[i]:=j;//记录路径
  if i=n then 
    begin
      if k=m then
        begin 
          for t:=1 to n do 
            write(tt[t],' ');
          writeln;
          inc(sum);
          if sum=100 then halt;//路径如果有100条了，则直接结束程序
        end;
      exit;
    end;
  if zz[i+1,j-1,k+j-1,2]=j then print(i+1,j-1,k+j-1);
  if zz[i+1,j+1,k+j+1,1]=j then print(i+1,j+1,k+j+1);//能否继续走
end;
begin
  readln(n,m);
  f[0,0]:=1;//边界
  ff:=f;
  for i:=2 to n do 
    begin
      inc(sum,i-1);
      for j:=-(i-1) to i-1 do  
        for k:=-sum to sum do 
          begin
            f[j,k]:=ff[j-1,k-j]+ff[j+1,k-j];
            if ff[j-1,k-j]>0 then zz[i,j,k,1]:=j-1; 
            if ff[j+1,k-j]>0 then zz[i,j,k,2]:=j+1;//记录路径
          end;
      ff:=f;//滚动数组
    end;//递推
  for i:=-100 to 100 do 
    inc(ans,f[i,m]);//计算总方案数
  sum:=0;
  writeln(ans);
  print(1,0,0);//递归输出路径
end.