题解

117 条题解

  • 0
    @ 2007-09-13 22:17:50

    终于`\交了11次我晕
    自己的方法超恶心\
    AC了再看题解 哎~牛人真的好多阿``

  • 0
    @ 2007-08-22 21:26:06

    第六组有问题吗?我也WA在那儿了。

  • 0
    @ 2007-08-13 23:30:15

    第六组是不是有问题?

  • 0
    @ 2007-07-22 20:17:23

    點解唔可以f(root, k) , k = 0, 1

    f(root, 1)表示放一個在root, f(root, 0)表示不放

    f(root, 1) = p(root) + Min { f( son_of(root), 0 or 1 ) }

    f(root, 0) = Min{ f( son_of(root), 0 or 1) } , 但至少有一個'1'

    且在葉子結點時作特別處理

    邊個可以講出有乜問題?

  • 0
    @ 2007-07-17 13:46:04

    ???????????????????????????????

    !!!!!!!!!!!!!!!!!!!!!!!

  • 0
    @ 2007-07-02 19:20:34

    终于会树形DP了

  • 0
    @ 2007-03-26 18:40:38

    编译通过...

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

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

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

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

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

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

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

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

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

    还可以,程序也就60行

  • 0
    @ 2007-03-19 21:57:40

    那个大牛给个正确程序看看呀,我使用卑鄙手段过的

  • 0
    @ 2007-02-01 21:44:00

    树型动态规划

    原题意似乎说这棵树节点的父子关系是指定的(也就是一张有向图),不过考虑到父子间可以互相控制,我用的无向图的方法把每条边作双向处理

    至于树根就用random随便找了(反正结果都一样)

    动态规划就有点恼火了

    对于任意i节点可能存在三种状态,用f表示三种状态下各自的最小代价(k=1~3):

    1、当前节点放守卫,受到控制(f);

    2、当前节点不放守卫,受到其子节点控制(f);

    3、当前节点不放守卫,也不受其子节点控制(f),此种情况下i节点必然将会被其父节点控制

    状态转移方程

    1、f=Σmin{f[j,1],f[j,2],f[j,3]|j为i所有子节点编号}+w[i](当前节点放守卫)

    2、f=Σmin{f[j,1],f[j,2]|j同上}+dis

    (这种情况下要保证i节点不放守卫但受到其子节点控制,必须至少有一个子节点要放守卫,如果所取的最小值全部都是由未放守卫的子节点取得的,就得从中选一个放守卫代价较小的,dis就是这个节点f[j,1]与f[j,2]的差,即dis=min{f[j,1]-min(f[j,1]-f[j,2])})

    3、f=Σf[j,2](j同上)

  • 0
    @ 2007-02-01 21:12:52

      一个每条边都是桥的图(即一棵树),对每个顶点进行染色,染色的方法是把

    该点和与其有边相连的点全部染上色,但是染色的代价是不一样的,这个代价等于

    那个点的某个权值,现用某种方案染色使这个图全部染色,问最少代价。

      这是一个典型的树形动态规划。“算法与数据结构”网站上有该题的解题报告,

    我的方法基本上是根据这个来的,具体的请到该网站查阅。

      大概思路,分三种情况,某个节点可能的三种情况,一是自己染色,二是由子

    节点染色,三是自己不染色,也不由子节点来担心,就把这个任务交给该节点的父

    节点了,这三种情况用不同的域来存。

      第一规划:该节点自己染色,子节点们就用自己三个域中的最小值(想一想为

    什么)

      第二规划:该节点由孩子来染色,但是由哪一个孩子来染色呢?不知道吧,那

    就枚举先,枚举子节点作为控制父节点的节点,其他节点全部用作能染色的类型,

    累加选最小的。

      第三规划:自己不染色,孩子也不来,就把这个任务交给父节点,那么该节点

    没有染色,该节点的子节点就必须能够自己染色,这种自己染色的情况又有两种,

    选一种最小的累加起来。

      

    不知道说的清楚不~~

  • 0
    @ 2007-02-01 21:26:17

    经典的树型DP

    本题既可以用有向树来做,也可以用无向图随机选根结点

    分析可见,对于当前结点i,它有num个子结点,它有它有3种状态:

    1:在当前位放置守卫的情况(被自己所控制)

    2:不在当前位放置守卫,但是它已经被它的子结点所控制

    3:不在当前位放置守卫,它还没有被它的子结点所影响(即被其父结点控制)

    用f表示结点i的第x种情况:

    1情况的值由其子结点的1,2,3情况得到最优

    2情况的值由其子结点的1,2情况得到最优

    3情况的值只可由其2情况求和.

    第2种情况要特别注意,要求它的子结点中必须有一个是1状况的,所以可以先将最小值求和,然后加上这num个子结点中每个的1情况与最优情况的f值之差--most

    方程:

    f:=Σ(min{f[son[j],1],f[son[j],2],f[son[j],3]})+a[i]

    f:=Σ(min{f[son[j],1],f[son[j],2]})+most

    f:=Σ(f[son[j],2]), 1

  • 0
    @ 2006-11-02 16:15:35

    感动。刚开始状态压缩得过于厉害,把正解都减掉了。深刻记忆。

  • 0
    @ 2006-09-24 15:20:48

    为什么就这样过了

    我还没想通呢!!

  • 0
    @ 2006-06-19 22:06:10

    个人认为难度应该改成2

    最基本的树型DP

    题目中似乎有个条件没说清楚吧

    树中父子节点可以互相看见

    别的都不行

  • -1
    @ 2019-07-15 11:51:17

    哈哈哈哈哈哈

  • -1
    @ 2018-02-26 22:12:06

    感谢*coolxxx*的题解!!!

  • -1
    @ 2016-08-08 16:19:07

    水题。亏我当时调了一下午,可惜思路不对
    用dfs_not表示当前节点未被保护的情况,dfs_did表示已经被保护的情况,**分类讨论**即可。
    ```c++
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;

    int n, m, rk[1550], rd[1550];
    int dp1[1550], dp2[1550];
    struct p {
    int to, next;
    }edge[4004];
    int head[1550], top = 0;
    void push(int i, int j)
    {
    rd[j]++;
    edge[++top].to = j;
    edge[top].next = head[i];
    head[i] = top;
    }
    int dfs_did(int);
    int dfs_not(int);

    int dfs_did(int nd)
    {
    if (dp1[nd] != -1) return dp1[nd];
    int ans = rk[nd];
    for (int i = head[nd]; i; i = edge[i].next)
    ans += dfs_did(edge[i].to);
    int a2 = 0;
    for (int i = head[nd]; i; i = edge[i].next)
    a2 += dfs_not(edge[i].to);
    return dp1[nd] = min(ans, a2);
    }

    int dfs_not(int nd)
    {
    if (dp2[nd] != -1) return dp2[nd];
    int ans = rk[nd];
    for (int i = head[nd]; i; i = edge[i].next) {
    int to = edge[i].to;
    ans += dfs_did(to);
    }
    dp2[nd] = ans;
    for (int i = head[nd]; i; i = edge[i].next) {
    int to = edge[i].to;
    int a2 = rk[to];
    for (int j = head[to]; j; j = edge[j].next)
    a2 += dfs_did(edge[j].to);
    for (int j = head[nd]; j; j = edge[j].next)
    if (j != i) {
    a2 += dfs_not(edge[j].to);
    }
    dp2[nd] = min(dp2[nd], a2);
    }
    return dp2[nd];
    }

    int main()
    {
    memset(rd, 0, sizeof rd);
    memset(head, 0, sizeof head);
    memset(dp1, -1, sizeof dp1);
    memset(dp2, -1, sizeof dp2);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
    int a, to;
    cin >> a;
    cin >> rk[a];
    cin >> m;
    for (int j = 1; j <= m; j++) {
    cin >> to;
    push(a, to);
    }
    }
    int rt = 0;
    for (int i = 1; i <= n; i++)
    if (rd[i] == 0) {
    rt = i;
    break;
    }
    cout << dfs_not(rt) << endl;
    return 0;
    }

信息

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