对于每个第二行的点与其有关的只有第一行的三个点，给左边的赋权1，中间的赋权2，右边的赋权4，那么对于每个点都有8个情况，分别对应0--7.而这个是没后效性的，可以用动规解，不多说，看代码。话说动规的代码真的好短。
program p1088; var x:array[0..20000,0..7] of int64; y:array[1..20000] of longint; i,j,n:longint; begin readln(n); for i:=1 to n do read(y[i]); fillchar(x,sizeof(x),0); x[0,0]:=1; x[0,4]:=1; for i:=1 to n-1 do if y[i]=0 then x[i,0]:=x[i-1,0]+x[i-1,1] else if y[i]=1 then begin x[i,1]:=x[i-1,2]+x[i-1,3]; x[i,2]:=x[i-1,4]+x[i-1,5]; x[i,4]:=x[i-1,0]+x[i-1,1]; end else if y[i]=2 then begin x[i,3]:=x[i-1,6]+x[i-1,7]; x[i,6]:=x[i-1,4]+x[i-1,5]; x[i,5]:=x[i-1,2]+x[i-1,3]; end else if y[i]=3 then x[i,7]:=x[i-1,6]+x[i-1,7]; if y[n]=0 then writeln(x[n-1,0]+x[n-1,1]) else if y[n]=1 then writeln(x[n-1,2]+x[n-1,3]+x[n-1,4]+x[n-1,5]) else if y[n]=2 then writeln(x[n-1,6]+x[n-1,7]); end.
评论 (0)
