题意:树的独立集(k<3)
又学到了 关于数据处理:
对于题目中这样的多叉树可以
1.转二叉树-->有的时候可以大幅改进效率(参见树状DP-选课的时间复杂度分析)
2.使用稀疏图的存法(前向星,邻接表)-->个人喜欢
题目有明显的最优子结构,可以使用动态规划.
然后题中给出的数据最开始很乱(无根树),缺乏拓扑序难以DP.
数据可达1e6,DFS爆栈,人工栈蛋疼.仔细想想,
这时不妨设1为根,跑一次BFS.
BFS给出的序列反过来就是拓扑序列,其深度递减.
再在这个拓扑序上跑DP就不用担心了
稍加思考可得,对于第一问状态表示只需要确定树根和树根是否选择.
并且第一问是最经典的树状DP之一,直接给方程
f[i,1]:以i为根的子树,取i时最大独立集的大小
f[i,0]:以i为根的子树,不取i时最大独立集的大小
f[i]=max(f[i,0],f[i,1])
f[i,0]=sigma(f[j])
f[i,1]=sigma(f[j,0])+1
其中j是i的儿子
时间O(V)*O(E/V) = O(E) = O(n)
对于第二问,明显也有最优子结构.
但是如果我们还沿用第一问的状态表示,方程很难想.
所以说不妨增加状态的表示,以求得方程.
题目中要求的是距离>2,所以想到了可以把
"i选不选"改为"i为根的子树中,所选择的距i最近的点距i的距离"
选自己则距离=0 选一个儿子不选自己则距离=1 etc
方程变为
f[i,j]:i为根的子树内,距i最近的选择点的距离为j时的最大独立集
再画图分析,考虑选择儿子孙子是的相互作用可得
f[i,0]=sigma(f[j,2])+1 //j是i的儿子,这种情况下没有冲突
f[i,1]=max(f[k,0]+f[j,1]) //k是i的某一个儿子,j是除k外的儿子,冲突存在于不能选择2个儿子
f[i,2]=sigma(f[j,1]) //j是i的儿子,无冲突
当然程序实现不必拘泥于此
这样第一问的方程可以改写.
时间O(kn)
NOIP2013
Rp:=5; Rp=Rp<<Rp;
while (1) { rp++; }
-其实我发这贴主要目的就是求RP--
渣码:
program rq719;
type pnode=^tnode;
tnode=record
n:longint;
next,opp,prev:pnode;
end;
-->用双向链表方便删除
var f:array[1..100000,-1..3] of longint;
g:array[1..100000] of pnode;
que:array[1..100000] of longint;
v:array[1..100000] of boolean;
n,k,top:longint;
function max(a,b:longint):longint; begin
if a>b then exit(a) else exit(b); end;
procedure init;
var tmp:pnode;
i,j,e1,e2:longint;
procedure ins(e1,e2:longint);
begin
new(tmp);
with tmp^ do begin
n:=e2;
next:=g[e1];
prev:=nil;
end;
if g[e1]<>nil then g[e1]^.prev:=tmp;
g[e1]:=tmp;
end;
begin
fillchar(g,sizeof(g),0);
fillchar(v,sizeof(v),0);
readln(n,k);
for i:=1 to n-1 do begin
readln(e1,e2);
ins(e1,e2);
ins(e2,e1);
g[e1]^.opp:=g[e2];
g[e2]^.opp:=g[e1];
end;
end;
procedure toposort;
var tmp:pnode;
down:longint;
begin
top:=n; down:=top; que[top]:=1;
while down>1 do begin
tmp:=g[que[top]];
dec(top);
while tmp<>nil do begin
if tmp^.opp^.prev<>nil then
tmp^.opp^.prev^.next:=tmp^.opp^.next
else g[tmp^.n]:=tmp^.opp^.next;
dec(down);
que[down]:=tmp^.n;
tmp:=tmp^.next;
end;
end;
end;
procedure work1;
var front,i,j,k,low,head:longint;
tmp:pnode;
begin
for front:=1 to n do begin
head:=que[front];
fillchar(f[head],sizeof(f[head]),0);
tmp:=g[head];
while tmp<>nil do begin
inc(f[head,0],f[tmp^.n,1]);
inc(f[head,1],f[tmp^.n,-1]);
tmp:=tmp^.next;
end;
inc(f[head,0]);
f[head,-1]:=max(f[head,0],f[head,1]);
end;
writeln(f[1,-1]);
end;
procedure work2;
var front,i,j,k,low,head,fact:longint;
tmp:pnode;
begin
for front:=1 to n do begin
head:=que[front];
fillchar(f[head],sizeof(f[head]),0);
tmp:=g[head];
fact:=0;
while tmp<>nil do begin
inc(f[head,0],f[tmp^.n,2]);
inc(f[head,1],f[tmp^.n,1]);
inc(f[head,2],f[tmp^.n,1]);
if f[tmp^.n,0]-f[tmp^.n,1]>fact then
fact:=f[tmp^.n,0]-f[tmp^.n,1];
tmp:=tmp^.next;
end;
inc(f[head,1],fact);
inc(f[head,0]);
end;
writeln(max(f[1,0],max(f[1,1],f[1,2])));
end;
begin
init;
toposort;
case k of
1:work1;
2:work2;
end;
end.
求NOIP2013 500+++++++