POJ2486&&POJ3659 ——树形动态规划

两道题都折腾了很长时间，总算过了。树形动规，主要在于动规顺序，其次才是状态的设计。

POJ2486：

先用左儿子右兄弟表示法进行多叉转二叉。

f[i][j]表示从i点出发走了j步、最后不一定要回到i点能吃到的最多苹果数

g[i][j]表示从i点出发走了j步、最后回到i点所能吃到的最多苹果数

动规方程比较复杂：

f[i][j]=Max{f[left[i],k],g[right[i],j-3-k]+a[i]}(0<=k<=j-3)

f[i][j]=Max{f[i,j],g[left[i],k]+f[right[i],j-4-k]+a[i]}(0<=k<=j-4)

g[i][j]=Max{g[i,k]+g[i,j-4-k]+a[i]}(0<=k<=j-4)

代码如下：

Program POJ2486;//By_Thispoet
Const
	maxn=105;
Var
	i,j,k,n,m,p,q,o,tmp					:Longint;
	f,g									:Array[0..maxn,0..maxn*2]of Longint;//f not back,g back
	a,left,right,re,father				:Array[0..maxn]of Longint;
	seq,pre,other,last					:Array[0..maxn*2]of Longint;
	h,t									:Longint;

Function Max(i,j:Longint):Longint;
begin
	if i>j then exit(i);exit(j);
end;


Procedure Bfs();
begin
	h:=0;t:=1;seq[1]:=1;
	while h<t do
		begin
			inc(h);
			i:=seq[h];
			j:=last[i];
			while j<>0 do
				begin
					k:=other[j];
					if k<>father[i] then
						begin
							father[k]:=i;
							if re[i]=0 then
								begin
									left[i]:=k;
									re[i]:=k;
								end else
								begin
									right[re[i]]:=k;
									re[i]:=k;
								end;
							inc(t);seq[t]:=k;
						end;
					j:=pre[j];
				end;
		end;
end;


BEGIN

	readln(n,o);
	while not eof do
		begin
			for i:=1 to n do read(a[i]);
			fillchar(father,sizeof(father),0);
			fillchar(f,sizeof(f),0);
			fillchar(g,sizeof(g),0);
			fillchar(re,sizeof(re),0);
			fillchar(left,sizeof(left),0);
			fillchar(right,sizeof(right),0);
			fillchar(last,sizeof(last),0);
			k:=0;
			for i:=1 to n-1 do
				begin
					readln(p,q);
					inc(k);pre[k]:=last[p];last[p]:=k;other[k]:=q;
					inc(k);pre[k]:=last[q];last[q]:=k;other[k]:=p;
				end;

			Bfs();

			while t>0 do
				begin
					i:=seq[t];
					for j:=0 to o do
						begin
							f[i,j]:=Max(f[right[i],j],a[i]);
							g[i,j]:=Max(g[right[i],j],a[i]);
							if j>=1 then
								begin
									f[i,j]:=Max(f[i,j],f[left[i],j-1]+a[i]);
								end;
							if j>=2 then
								begin
									f[i,j]:=Max(f[i,j],f[right[i],j-2]+a[i]);
									g[i,j]:=Max(g[i,j],g[left[i],j-2]+a[i]);
									g[i,j]:=Max(g[i,j],g[right[i],j-2]+a[i]);
								end;
							for k:=0 to j-3 do
								begin
									f[i,j]:=Max(f[i,j],f[left[i],k]+g[right[i],j-3-k]+a[i]);
								end;
							for k:=0 to j-4 do
								begin
									g[i,j]:=Max(g[i,j],g[left[i],k]+g[right[i],j-4-k]+a[i]);
									f[i,j]:=Max(f[i,j],g[left[i],k]+f[right[i],j-4-k]+a[i]);
								end;
						end;
					dec(t);
				end;

			writeln(f[1,o]);

			readln(n,o);
		end;

END.
           

POJ3659:

f[i][0]表示i这个点依赖于子节点的电话亭，且以i为根的子树全部被覆盖时所用的最少电话亭数

f[i][1]表示i这个点建电话亭且满足上述条件的最少电话亭数

f[i][2]表示i这个点依赖于父节点的电话亭求满足上述条件的最少电话亭数

状态转移方程很简单，直接看代码就能懂的：

Program Tower;//By_Thispoet
Const
	maxn=10005;
Var
	i,j,k,n,h,t,p,q					:Integer;
	f								:Array[1..maxn,0..2]of Integer;
	pre,other,last,seq				:Array[1..maxn*2]of Integer;
	father,leaf						:Array[1..maxn]of Integer;

Function Min(i,j:Longint):Longint;
begin
	if i<j then exit(i);exit(j);
end;


Procedure Bfs();
begin
	h:=0;t:=1;seq[t]:=1;
	while h<t do
		begin
			inc(h);
			i:=seq[h];
			j:=last[i];
			while j<>0 do
				begin
					k:=other[j];
					if k<>father[i] then
						begin
							father[k]:=i;
							leaf[i]:=1;
							inc(t);seq[t]:=k;
						end;
					j:=pre[j];
				end;
		end;
end;
	
	
Procedure Dp();
var flag:Boolean;
	mini:Longint;
begin
	while t>0 do
		begin
			i:=seq[t];
			flag:=false;
			if leaf[i]=0 then
				begin
					f[i,0]:=maxint;
					f[i,1]:=1;
					f[i,2]:=0;
				end else
					begin
						j:=last[i];
						while j<>0 do
							begin
								k:=other[j];
								if k<>father[i] then 
									begin
										if f[k,1]<=f[k,0] then
											begin
												flag:=true;
												inc(f[i,0],f[k,1]);
											end else inc(f[i,0],f[k,0]);
										inc(f[i,1],Min(f[k,1],f[k,2]));
										inc(f[i,2],Min(f[k,1],f[k,0]));
									end;
								j:=pre[j];
							end;
						inc(f[i,1]);
						if not flag then inc(f[i,0]);
					end;
			dec(t);
		end;
end;


BEGIN

	readln(n);
	for i:=1 to n-1 do
		begin
			readln(p,q);
			inc(k);pre[k]:=last[p];last[p]:=k;other[k]:=q;
			inc(k);pre[k]:=last[q];last[q]:=k;other[k]:=p;
		end;

	Bfs();
	fillchar(f,sizeof(f),0);

	Dp();
	writeln(Min(f[1,0],f[1,1]));

END.
           

转载于:https://www.cnblogs.com/Thispoet/archive/2011/09/27/2192876.html