题解

117 条题解

  • 0
    @ 2014-02-05 21:06:28

    测评机泥垢了。。。runtime error加上一个return 0就过了=_=

  • 0
    @ 2013-09-30 16:41:10

    测试数据 #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

  • 0
    @ 2013-09-30 16:40:52

    测试数据 #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
    @ 2013-09-30 16:39:23

    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
    @ 2013-07-07 19:16:49

    莫名其妙地过了~还担心有什么特殊情况没想到。。
    f[i,1]表示i点守
    f[i,2]表示i点不守,father[i]守
    f[i,3]表示i点不守,father[i]不守
    然后就是乱写了0 0

    type
    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;
    begin

    read(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
    @ 2012-10-13 12:01:20

    分三种情况讨论啊啊,想练习树形DP的同学在纸上仔细划分一下情况,注意细节!

    根直接看入度就行

  • 0
    @ 2012-07-25 16:40:07

    编译通过...

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

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

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

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

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

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

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

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

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

    一次AC 树形动规

  • 0
    @ 2010-04-15 15:35:19

    弱了我……

    悲剧般的树形动归

    悲剧般的转移方程

  • 0
    @ 2010-03-18 19:57:00

    关键的f[son[j],1]

  • 0
    @ 2009-11-09 17:55:55

    ....方程写错了竟然还对了三个点

  • 0
    @ 2009-11-07 13:25:46

    根节点不一定是1……

  • 0
    @ 2009-11-02 00:36:01

    编译通过...

    ├ 测试数据 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
    @ 2009-10-28 19:00:23

    膜拜1S神牛

    话说,今天我的智商已经不支持我做这种题了,全靠1S的题解.....

  • 0
    @ 2009-10-26 20:53:29

    还真囧死了今天。。

    程序都是调了好久才AC,算法什么都没错,就是maxn的设置出了问题

  • 0
    @ 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
    @ 2009-10-23 20:07:41

    我和大牛们的看法有点不同啊:

    ①f:=∑min{f[son,1],f[son,2],f[son,3]}+a[i];

    ②f:=∑min{f[son,1],f[son,2]}+m;

    {m=min{f[son,1]-f[son,2]}}

    讨论m:

    当m>0时,相对于每个子节点j最优状态都为f[j,2],此时应该弥补一下,使其满足②;

    当mi,且为其子节点}。

  • 0
    @ 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
    @ 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***|

    看了之后只有加*号的地方不是很懂,于是自己想了个办法:

    对于当前结点X的儿子(不妨设为K),每次求出MIN(F[K,1],F[K,2])后,作差:

    差=F[K,1]-MIN; 每次让F[X,2]:=F[X,2]+MIN;

    当所有的儿子都遍历完成后,再让F[X,2]加上所有的作的差中最小的那个差

    (如果在选取某个MIN(F[K,1],F[K,2])时,选中了F[K,1],则所作的差为0,显然这个差是最小的;没有选中的情况类似)。。。。。

    最后一个注意点:

    当某个点K的出度为0时(即K为叶子结点),这时候F[K,2]这个状态是不存在的,所以要让F[K,2]取无穷(可以是maxlongint);

  • 0
    @ 2009-10-11 12:52:49

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

    太悲剧了,第一次居然少了最重要的一句话,样例都能过.....

    想了个非常弱智的方程,多叉树dfs(n才只有1500啊..),但是总觉得这个太麻烦,不自信地看了看各位大牛题解,居然也都只是这样的方法,难道就没有更好的方法?

  • 0
    @ 2009-10-08 21:35:02

    第二个点错的人注意

    题目给得数据有问题 它的边不是按1,2。。。。i 的顺序给的

信息

ID
1144
难度
7
分类
动态规划 | 树形DP 点击显示
标签
递交数
4561
已通过
1001
通过率
22%
被复制
10
上传者