6.1.1.pas

usacoCHAPTER6程序,非常恶心的动态规划转移方程,位运算等等

{
ID:LXYXYNT3
PROB:vans
LANG:PASCAL
}
const
  inf='vans.in';
  ouf='vans.out';
  maxn=1000;
  maxm=8;
  base=100000000;
  base1=8;

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

var
  dp:array[1..maxn+1,1..maxm] of arr;
  i,j,m,n:longint;

procedure add(a:arr;var b:arr);
var
  i,k:longint;
begin
  if a[0]>b[0] then b[0]:=a[0];
  for i:=1 to b[0] do inc(b[i],a[i]);
  i:=1;
  while i<=b[0] do
  begin
    if b[i]>=base then
    begin
      inc(b[i+1],b[i] div base);
      b[i]:=b[i] mod base;
      if i=b[0] then inc(b[0]);
    end;
    inc(i);
  end;
end;

procedure print(a:arr);
var
  i:longint;
  s:string;
begin
  write(a[a[0]]);
  for i:=a[0]-1 downto 1 do
  begin
    str(a[i],s);
    while length(s)<base1 do s:='0'+s;
    write(s);
  end;
  writeln;
end;

begin
  assign(input,inf);reset(input);
  assign(output,ouf);rewrite(output);
  readln(n);
  if n=1 then
  begin
    writeln(0);
    close(input);
    close(output);
    halt;
  end;
  fillchar(dp,sizeof(dp),0);
  dp[1,3,0]:=1;dp[1,3,1]:=1;
  dp[1,7,0]:=1;dp[1,7,1]:=1;
  for i:=2 to n-1 do
  begin
    add(dp[i-1,3],dp[i,1]);
    add(dp[i-1,8],dp[i,1]);
    add(dp[i-1,1],dp[i,3]);
    add(dp[i-1,4],dp[i,3]);
    add(dp[i-1,6],dp[i,3]);
    add(dp[i-1,7],dp[i,3]);
    add(dp[i-1,3],dp[i,4]);
    add(dp[i-1,3],dp[i,6]);
    add(dp[i-1,8],dp[i,6]);
    add(dp[i-1,1],dp[i,7]);
    add(dp[i-1,6],dp[i,7]);
    add(dp[i-1,7],dp[i,7]);
    add(dp[i-1,3],dp[i,8]);
    add(dp[i-1,8],dp[i,8]);
  end;
  add(dp[n-1,3],dp[n,2]);
  add(dp[n-1,8],dp[n,2]);
  add(dp[n,2],dp[n,2]);
  print(dp[n,2]);
  close(input);
  close(output);
end.