三种状态

1.自己守卫

2.儿子守卫

3.每人守卫

1=1+min（1,2,3）

2=2+min(1,2)(至少一个1)

3=3+2(儿子的)

{min是儿子的}

f表示儿子都被看守但自己没有被看守所花费的最小代价

f表示儿子和自己都被看守，但是自己没有派人，所花费的最小代价

f表示儿子和自己都被看守并且自己也派人看守了，儿子和自己都被看守

另外由于n最大为1500，所以存储儿子用拉链法（即多叉树转二叉树存储法）

我的递归程序（用宽搜球拓扑序列然后再动归也可以）

var o,i,n,j,p,r,l,k:integer;

a,fu,q,link:array[1..1500] of integer;

f:array[1..1500,1..3] of longint;

function s(x,y,z:longint):longint;

begin

s:=x; if y

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

root 算错了 大悲剧啊

Flag 　　Accepted

题号 　　P1144

类型(?) 　　动态规划

通过 　　777人

提交 　　3469次

通过率 　　22%

难度 　　3

第777个

7是有魔力的数字啊~~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

水题……DFS一下就行了

#include

#include

#include

#define maxint 2100000000

#define maxn 1501

typedef struct type{ long k;struct type * next;}list;

long Root,B[maxn]={0},D[maxn][3]={0},P[maxn]={0},Ans,N,M;

list *e[maxn]={0};

long min(long a,long b,long c){

long x=a;

if (x>b) x=b;

if (x>c) x=c;

return x;

}

void Add(long x,long y){

list *p=(list*)malloc(sizeof(list));

p->k=y;

p->next=e[x];

e[x]=p;

}

void DFS(long v){

list *p,*q;

if (!e[v]) return;

if (D[v][2]) return;

long Sum0=0,Sum1=0,Sum2=0;

for (p=e[v];p;p=p->next)

DFS(p->k);

for (p=e[v];p;p=p->next){

Sum0+=D[p->k][1];

Sum2+=min(D[p->k][0],D[p->k][1],D[p->k][2]);

}

D[v][1]=99999999;

for (p=e[v];p;p=p->next){

Sum1=D[p->k][2];

for (q=e[v];q;q=q->next)

if (p!=q) Sum1+=min(D[q->k][1],D[q->k][2],maxint);

D[v][1]=min(Sum1,D[v][1],maxint);

}

D[v][0]=Sum0;

D[v][2]=P[v]+Sum2;

}

int main(void){

long i,j,x,y,p,z;

scanf("%ld",&N);

for (i=0;i

比较简单的树归,可惜没能1A...

解法:

f[i],i点有人时,以i为根的子树的最小费用.

a[i]为当i点没人时,i点被守卫(即其子节点中至少有一个点有人)的最小费用.

b[i]为当i点没人时,i点未被守卫的最小费用.

状态转移方程:

f[i]:=f[i]+min(f[k],a[k],b[k]);

a[i]:=a[i]+min(f[k],a[k]);(但要保证a[i]加了一次f[*],否则稍微调整,使调整的代价最小)

b[i]:=b[i]+a[k];

ans:=max(f[root],a[root]);

f[i][j][k]表示i节点，父亲是否有填，父亲是否被覆盖

转移O(1)

这题cjf在绍兴时出了加强版

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

谢谢大牛们的题解，让我这道了树形DP

第2组1019输出1001等答案的OIer们。。。

我也是这样。。

我改完完AC的原因是。。1不一定是根。。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

whyvine的解题报告：

http://blog.sina.com.cn/s/blog_618b6ea70100eglq.html

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/36065179_d.html

是不是处理前要拓扑排序啊？

我看了大牛们的题解，至少文字里没说，我也没看源代码

感动中……在交了4次以后

有很多大牛写了题解，我就少废话

总之状态的转移既和孩子们有关，也和自己的父亲有关

所以要多设一个状态，描述父亲的影响

长辈的力量还真是大

程序60行

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

啊 总算秒了

树形DP从来都是逃避不做的

没想到其实蛮简单的

这一题主要思想在别人的博客中

http://hi.baidu.com/pjww/blog/item/e6fb1f2d9ccb7c37359bf7e3.html

可以去看看

本来昨天做好交上去 只有29分？？？（29分怎么测出来的？？？）

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案错误...程序输出比正确答案长

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：29 有效耗时：0ms

然后就是找不到错误......

但是急着回家，就先放下了

..........

今天早上重新看了一遍

结果发现 本来f[k,1]应该是子节点的最小值+cost[k](本身的费用)

但是我昨天的程序一不小心把cost[k]放到循环里....

结果每加一个子节点的值就加了一次cost[i].......

还有注意f[k,2]（即本节点不设守卫，由子节点得出）

因为有可能出现全部由子节点的2情况得出 （但是子节点中至少要含有一个子节点为1的情况）

所以要另外判断一下.........

---|---|---|---|---|---|---|---|---|---|晒程序---|---|---|---|---|---|---|---|---|---|

program p1144;

var root,n:longint;

cost,nums:array[0..1505] of longint;

t:array[0..1505] of boolean;

son:array[0..1505,0..1505] of integer;

f:array[0..1505,1..3] of longint;

procedure init;

var x,k,m,i,j:longint;

begin

fillchar(t,sizeof(t),true);

readln(n);

for i:=1 to n do

begin

read(x,k,m);

cost[x]:=k; nums[x]:=m;

for j:=1 to m do

begin

read(son[x,j]);

t[son[x,j]]:=false;

end;

readln;

end;

for i:=1 to n do if t[i] then

begin

root:=i;

break;

end;

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

for i:=1 to n do if nums[i]=0 then

begin

f:=cost[i];

f:=99999999;

f:=0;

end;

end;

function min(a,b:longint):longint;

begin

if a>b then min:=b else min:=a;

end;

procedure work(k:longint);

var i,j,temp:longint;

begin

if nums[k]=0 then exit;

for i:=1 to nums[k] do work(son[k,i]);

temp:=99999999;

for i:=1 to nums[k] do

begin

f[k,1]:=f[k,1]+min(min(f[son[k,i],1],f[son[k,i],2]),f[son[k,i],3]);

f[k,2]:=f[k,2]+min(f[son[k,i],1],f[son[k,i],2]);

if f[son[k,i],1]-min(f[son[k,i],1],f[son[k,i],2])

690 ACer

最后两组数据，用maxint不够，用maxlongint会超

有个好办法：把类型定义为int64，做完一个点，把大于maxlongint的数据赋为maxlongint

最小控制集？据说是对每个叶子将小胖放到父亲上。。然后把小胖能看到的都给删了。。接着搞啊搞啊。。就出来了吧。。

第一次错误方程：

d[i]表示守i和它的子树的最小花费（选i）

p[i]表示守i和它的子树的最小花费（不选i）

d[i]=∑(p)+cost[i]

p[i]=min{d[k]+∑(p[i的儿子except k]) | k是i的一个儿子}

本来打算从叶子结点往上递推，后来发现当树右偏时不行，只能DFS记忆化。

接着测样例发现错误。需要3个状态。

第二次错误方程：

f1[i]表示守当前i，f2[i]表示i被父亲守，f3[i]表示i被儿子守

f1[i]=∑f2+cost[i]

f2[i]=∑min{f1,f3}

f3[i]=min{f1[k]+∑min{f1[i的儿子except k],f3[i的儿子except k]}}

提交后WA1个点。看题解发现f1错误。

正确方程：

f1[i]=∑min{f1,f2,f3}+cost[i]

（其他和第二次一样）

PS.某人的题解中f2直接用∑f3，个人认为是错误的。

秒杀，不错不错，一开始由于三种情况只考虑了两个而WA了N次。

program vijos;

var i,j,k,n,m,max,tot:longint;

boo:boolean;

b:array[1..1500] of boolean;

d,dd:array[1..1500,1..1500] of integer;

l,ll,lll,w:array[1..1500] of integer;

f:array[1..1500,-1..1] of longint;

function min(x,y:longint):longint;

begin

if x

type

link=^node;

node=record

son:longint;

next:link;

end;

var

a:array[1..1500]of link;

f:array[1..1500,1..3]of longint;

visit:array[1..1500]of boolean;

stack,w:array[1..1500]of longint;

i,j,k,m,x,n,root:longint;

pd:boolean;

function min(x,y:longint):longint;

begin

if x>y then exit(y) else exit(x);

end;

procedure init(var p:link;x:longint);

var

q:link;

begin

new(q);

q^.next:=p;

q^.son:=x;

p:=q;

end;

procedure work(j:longint);

var

p,q:link;

min1,t,s:longint;

pd:boolean;

begin

if visit[j] then exit;

visit[j]:=true;

if a[j]=nil then

begin

f[j,1]:=w[j];

f[j,2]:=maxlongint;

f[j,3]:=0;

dispose(a[j]);

exit;

end;

p:=a[j];

min1:=maxlongint;

pd:=false;

t:=0;

s:=0;

while pnil do

begin

if not visit[p^.son] then work(p^.son);

if f[p^.son,1]>f[p^.son,2] then

begin

inc(t,f[p^.son,2]);

min1:=min(min1,f[p^.son,1]-f[p^.son,2]);

end

else

begin

pd:=true;

inc(t,f[p^.son,1]);

end;

inc(s,min(min(f[p^.son,1],f[p^.son,2]),f[p^.son,3]));

q:=p;

p:=p^.next;

dispose(q);

end;

dispose(p);

inc(f[j,1],w[j]+s);

f[j,3]:=t;

f[j,2]:=t;

if not pd then inc(f[j,2],min1);

end;

begin

read(n);

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

fillchar(visit,sizeof(visit),false);

for i:=1 to n do

begin

read(j,k,m);

w[j]:=k;

new(a[j]);

a[j]:=nil;

for k:=1 to m do

begin

read(x);

visit[x]:=true;

init(a[j],x);

end;

stack[i]:=j;

end;

for i:=1 to n do if not visit[i] then begin root:=i;break; end;

fillchar(visit,sizeof(visit),false);

for i:=n downto 1 do

work(stack[i]);

writeln(min(f[root,1],f[root,2]));

end.

第2个点好赖呀..答1019或8019的注意了，是数据输入的问题，他给的房子不一定是按照编号1~n的顺序，所以读的编号不能省..折腾半天终于发现了...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

f表示在i点放小胖

f表示不在i点放小胖，但被子节点控制。

f表示不在i点放小胖，也没被子节点控制。

规划方程：

如果i是子节点，则

f:=w[i];

f:=maxint;

f:=0;

否则

f:=f+min(min(f[son,1],f[son,2]),f[son,3])

f:=f+min(f[son,2],f[son,1]);

f:=f+f[son,2];

但有一个问题，在f中，如果都选f[son,2],那么i就不会被控制，矛盾，所以要加上一句：

if f[son,1]-min(f[son,1],f[son,2])