8
20
2013
0

【BZOJ1088】【SCOI2005】扫雷Mine【DP】

对于每个第二行的点与其有关的只有第一行的三个点,给左边的赋权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.
Category: DP | Tags: | Read Count: 915

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com