117 条题解
-
0
td650769 LV 8 @ 2014-02-05 21:06:28
测评机泥垢了。。。runtime error加上一个return 0就过了=_=
-
0
测试数据 #0: Accepted, time = 0 ms, mem = 9676 KiB, score = 14
测试数据 #1: Accepted, time = 0 ms, mem = 9676 KiB, score = 14
测试数据 #2: Accepted, time = 0 ms, mem = 9676 KiB, score = 14
测试数据 #3: Accepted, time = 15 ms, mem = 9728 KiB, score = 14
测试数据 #4: Accepted, time = 0 ms, mem = 9676 KiB, score = 14
测试数据 #5: Accepted, time = 15 ms, mem = 9676 KiB, score = 14
测试数据 #6: Accepted, time = 0 ms, mem = 9676 KiB, score = 14
-
1111111129 @ 2014-08-11 21:28:55
orzorz
-
-
0
测试数据 #0: Accepted, time = 0 ms, mem = 9676 KiB, score = 14
测试数据 #1: WrongAnswer, time = 15 ms, mem = 9676 KiB, score = 0
测试数据 #2: Accepted, time = 0 ms, mem = 9676 KiB, score = 14
测试数据 #3: Accepted, time = 15 ms, mem = 9728 KiB, score = 14
测试数据 #4: Accepted, time = 0 ms, mem = 9676 KiB, score = 14
测试数据 #5: Accepted, time = 0 ms, mem = 9676 KiB, score = 14
测试数据 #6: Accepted, time = 0 ms, mem = 9676 KiB, score = 14
这是第一次提交后的结果。
原来，
根不一定是第一个点！！！！ -
0
var
a,data,num,father:array[0..1500] of longint;
f:array[0..1500,1..3] of longint;
map:array[0..1500,0..1500] of longint;
i,n,ch,j,now,root:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a);
exit(b);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a);
exit(b);
end;
function try(k,p:longint):longint;
var
m,go,extra,i:longint;
begin
if (f[k,p]>0) or (k=0) then exit(f[k,p]);
if num[k]=0 then
begin
f[k,1]:=data[k];
f[k,2]:=maxlongint;
f[k,3]:=0;
exit(f[k,p]);
end;
if p=1 then
begin
f[k,p]:=data[k];
for i:=1 to num[k] do
begin
go:=map[k,i];
m:=min(min(try(go,1),try(go,2)),try(go,3));
f[k,p]:=f[k,p]+m;
end;
exit(f[k,p]);
end;
if p=2 then
begin
extra:=maxlongint;
for i:=1 to num[k] do
begin
go:=map[k,i];
m:=min(try(go,1),try(go,2));
if f[go,1]-min(f[go,1],f[go,2])<extra then
extra:=f[go,1]-min(f[go,1],f[go,2]);
f[k,p]:=f[k,p]+m;
end;
f[k,p]:=f[k,p]+extra;
exit(f[k,p]);
end;
for i:=1 to num[k] do
begin
go:=map[k,i];
m:=min(try(go,1),try(go,2));
f[k,p]:=f[k,p]+m;
end;
exit(f[k,p]);
end;
function find(k:longint):longint;
begin
if father[k]=0 then exit(k);
exit(find(father[k]));
end;
begin
readln(n);
for i:=1 to n do
begin
read(now);
read(data[now]);
read(num[now]);
for j:=1 to num[now] do
begin
read(ch);
map[now,j]:=ch;
father[ch]:=now;
end;
readln;
end;
root:=find(1);
writeln(min(try(root,1),try(root,2)));
end. -
0
莫名其妙地过了～还担心有什么特殊情况没想到。。
f[i,1]表示i点守
f[i,2]表示i点不守，father[i]守
f[i,3]表示i点不守，father[i]不守
然后就是乱写了0 0type
cc=record
n,v:Longint;
end;
var
f:array[0..1501,1..3]of longint;
t,a:array[0..1501]of longint;
q:array[0..2000]of cc;
i,j,k,m,n,p,root,top:Longint;
procedure init;
var
b:array[0..1501]of boolean;
beginread(n);
fillchar(b,sizeof(b),true);
for i:=1 to n do
begin
read(j);
read(a[j],m);
for k:=1 to m do
begin
inc(top);
read(q[top].v);
b[q[top].v]:=false;
q[top].n:=t[j];
t[j]:=top;
end;
end;
for i:=1 to n do
if b[i] then
root:=i;
end;
function min(a,b:Longint):Longint;
begin
if a<b then exit(a);
exit(b);
end;
function dp(x,y:longint):Longint;
var
i,j,k,z,c:Longint;
bo:boolean;
begin
if f[x,y]<>0 then exit(f[x,y]);
k:=t[x];
if y=1 then
begin
f[x,y]:=a[x];
while k>0 do
begin
z:=q[k].v;
inc(f[x,y],min(dp(z,1),dp(z,2)));
k:=q[k].n;
end;
exit(f[x,y]);
end;
if y=2 then
begin
while k>0 do
begin
z:=q[k].v;
inc(f[x,y],min(dp(z,3),dp(z,1)));
k:=q[k].n;
end;
exit(f[x,y]);
end;
if y=3 then
begin
if k=0 then
begin
f[x,y]:=maxlongint shr 2;
exit(f[x,y]);
end;
c:=maxlongint;
while k>0 do
begin
z:=q[k].v;
if c>dp(z,1)-dp(z,3) then
c:=f[z,1]-f[z,3];
inc(f[x,y],min(f[z,3],f[z,1]));
k:=q[k].n;
end;if c>=0 then
inc(f[x,y],c);
exit(f[x,y]);
end;
end;begin
init;
dp(root,3);
writeln(min(dp(root,1),dp(root,3)));
end. -
0
silence_sure LV 8 @ 2012-10-13 12:01:20
分三种情况讨论啊啊，想练习树形DP的同学在纸上仔细划分一下情况，注意细节！
根直接看入度就行 -
0
sliverzero LV 8 @ 2010-03-18 19:57:00
关键的f[son[j],1]
-
0
llx2192716 LV 8 @ 2009-11-07 13:25:46
根节点不一定是1……
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms三种状态：1、自守
2、子守
3、父守
方程:f:=Σ(min{f[son,1],f[son,2],f[son,3]})+a[i]
f:=Σ(min{f[son,1],f[son,2]})+m
f:=Σ(f[son,2])
第2种情况要特别注意,要求它的子结点中必须有一个是1状况的,所以令m=min{f[son[j],1]-f[son[j],2]},如果m>0说明在决策的时候，它的子结点没有一个是1状况的，这样就要加上m,否则令m=0.
========================树dp的分割线=======================
program v1144;
const maxn=100000000000000;
var l,r,w:array[0..1501] of longint;
f:array[0..1501,1..3] of int64;
i,j,n,root,p,m,x,k:longint;
function min(p,q:int64):int64;
begin
if p -
0
prince_hao LV 10 @ 2009-10-24 18:57:28
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms额额 1不一定是根啊
预处理出一棵以1为根的树 -
0
SecretAgent LV 10 @ 2009-10-19 07:44:50
题中给的有向图，所以要递归出根再DP。
或者把图转成无向图，
然后以某个结点宽搜出一棵树再DP。
DP方法见楼下说明编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
song19931218 LV 9 @ 2009-10-18 11:09:12
参考了凝风阁主人 1s 大牛的题解。。秒杀；
一开始想错了DP方程，反正是错的很离谱，错的一塌糊涂，但是竟然也A了43分，可见vj的数据真的很弱。。。。
ps下1s大牛的解答：
本题既可以用有向树来做,也可以用无向图随机选根结点分析可见,对于当前结点i,它有num个子结点,它有它有3种状态:
1:在当前位放置守卫的情况(被自己所控制)
2:不在当前位放置守卫,但是它已经被它的子结点所控制
3:不在当前位放置守卫,它还没有被它的子结点所影响(即被其父结点控制)
用f表示结点i的第x种情况:
1情况的值由其子结点的1,2,3情况得到最优
2情况的值由其子结点的1,2情况得到最优
3情况的值只可由其2情况求和.
***|第2种情况要特别注意,要求它的子结点中必须有一个是1状况的,所以可以先将最小值求和,
然后加上这num个子结点中每个的1情况与最优情况的f值之差--most***|
看了之后只有加*号的地方不是很懂，于是自己想了个办法：
对于当前结点Ｘ的儿子（不妨设为Ｋ),每次求出MIN（F[K,1],F[K,2])后，作差：
差＝Ｆ［Ｋ，１］－ＭＩＮ； 每次让Ｆ［Ｘ，２］：＝Ｆ［Ｘ，２］＋ＭＩＮ；
当所有的儿子都遍历完成后，再让Ｆ［Ｘ，２］加上所有的作的差中最小的那个差
（如果在选取某个ＭＩＮ（Ｆ［Ｋ，１］，Ｆ［Ｋ，２］）时，选中了Ｆ［Ｋ，１］，则所作的差为０，显然这个差是最小的；没有选中的情况类似）。。。。。
最后一个注意点：
当某个点Ｋ的出度为０时（即Ｋ为叶子结点），这时候Ｆ［Ｋ，２］这个状态是不存在的，所以要让Ｆ［Ｋ，２］取无穷（可以是maxlongint);
td650769
LV 8
@ 2014-02-05 21:06:28
