题解

117 条题解

  • 4
    @ 2017-10-05 21:50:31
    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const int maxn = 1550;
    int n, cost[maxn], dp[maxn][3];
    bool root[maxn];
    vector<int> G[maxn];
    
    void dfs(int u) {
        int _min = 0x3f3f3f3f;
        for (int v : G[u]) {
            dfs(v);
            dp[u][0] += min(min(dp[v][0], dp[v][1]), dp[v][2]);
            dp[u][1] += min(dp[v][0], dp[v][1]);
            dp[u][2] += min(dp[v][0], dp[v][1]);
            _min = min(_min, dp[v][0] - min(dp[v][0], dp[v][1]));
        }
        dp[u][0] += cost[u];
        dp[u][1] += _min;
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin >> n;
        for (int i = 1; i <= n; i++) {
            int u, c, m, v;
            cin >> u >> c >> m;
            cost[u] = c;
            while (m--) {
                cin >> v;
                root[v] = true;
                G[u].push_back(v);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!root[i]) {
                dfs(i);
                cout << min(dp[i][0], dp[i][1]) << endl;
                break;
            }
        }
        return 0;
    }
    
  • 3
    @ 2017-10-05 21:52:27

    f[0][x] 表示以x为根的子树已经被控制好,且x也被控制好,x放守卫。
    f[1][x] 表示以x为根的子树已经被控制好,且x也被控制好,x不放守卫。
    f[2][x] 表示以x为根的子树已经被控制好,但x没有被控制,且x不放守卫。
    f[0][x]=∑min{f[0][y],f[1][y],f[2][y]}+a[x]; (y是x的直系儿子节点)
    f[1][x]=∑min{f[0][y],f[1][y]}+(f[0][u]-f[1][u]);右半部分括号内的东西在y全都不放守卫时起作用。且(f[0][u]-f[1][u])min;
    f[2][x]=∑f[1][y];

  • 2
    @ 2016-08-20 23:32:31

    链式前向星+动态规划。有点坑。看代码注释去。
    ```cpp
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <cctype>
    #include <climits>
    #include <algorithm>
    #include <map>
    #include <queue>
    #include <vector>
    #include <ctime>
    #include <string>
    #include <cstring>
    using namespace std;
    #define INF 100000000
    //不用数了,上面是1亿,9位,8个0.
    int to[3001],pre[6001],last[6001];//链式前向星各数组
    int dp[3001][3];//f(i,j)对于编号i的点,j=0表示由子节点守卫时最小花费,j=1表示由自己守卫最小花费,j=2表示由父节点守卫最小花费
    int cost[3001];//顾名思义
    int id=0;//给边编号用
    void add(int a,int b)//连一条a->b的单向线
    {
    pre[++id]=last[a];//标记同样由a出发的上一条边是哪条
    to[id]=b;//标记这条边连向b
    last[a]=id;//标记最后一条边为这条边
    }
    void dfs(int now,int father)
    {
    dp[now][1]=cost[now];
    dp[now][2]=0;
    //上为初始化
    int flag=INF;//flag是精华!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    for(int i=last[now]; i; i=pre[i]) {//枚举以now这个点为起点的每一条边
    if(to[i]!=father) {//如果某一个点和他连接又不是父节点,那就是子节点。
    dfs(to[i],now);//要由叶子节点推到根节点。dfs下一层

    dp[now][0]+=min(dp[to[i]][1],dp[to[i]][0]);
    //前者优时,状态确定。父节点(to[i])更划算,守卫!
    //当后者优时,状态不确定:now让子节点守护,这个子节点又让子节点守护,不清真!
    dp[now][1]+=min(dp[to[i]][1],min(dp[to[i]][2],dp[to[i]][0]));//状态确定。
    dp[now][2]+=min(dp[to[i]][0],dp[to[i]][1]);//状态确定。
    //以下处理dp[now][0]巨坑。
    if(dp[to[i]][1]<=dp[to[i]][0]) //now节点的这个儿子自己有了守卫(同时守卫了now),不用强迫放置守卫于某个子节点(to[i])
    flag=0;
    if(flag&&dp[to[i]][1]-dp[to[i]][0]<flag) {
    //万一父节点没放(to[i])可能要必须放(出现dp[now][0]求值时min函数中后者优的情况,
    //必须有一个子节点(to[i])来保护父节点(now)),记录放父节点和原来所增加的额外费用。
    //(当然如果某个子节点已经保护了,补差价0元:不用强迫放置守卫于子节点(to[i]))
    //如果都没保护父节点(now),挑一个最划算的,补最小的差价,差价最小多少?没错,在flag里。
    flag=dp[to[i]][1]-dp[to[i]][0];//得出:子节点(to[i])自己守卫 & 子节点(to[i])由其子节点(to[i]的子节点)守卫 的差价。 强行放守卫贵了flag这么多。
    }
    }
    }
    dp[now][0]+=flag;//补差价
    }
    int main()
    {
    int n;
    scanf("%d",&n);//n个节点
    for (int i=1;i<=n;i++) {
    int a,b,k;
    scanf("%d",&a);//节点编号
    scanf("%d",&cost[a]);//节点放置守卫经费
    scanf("%d",&k);//子节点数
    while(k--) {
    scanf("%d",&b);//子节点
    add(a,b);//a->b
    add(b,a);//b->a
    //子节点父节点连边,注意双向
    }
    }
    dfs(1,0);//作用:由下往上推,最后守卫网络将覆盖到编号为1的点(根节点) ,搞到这时的最小花费 。第二个参数为父节点,根节点(节点1)无父节点,传入0.
    printf("%d",min(dp[1][0],dp[1][1]));//输出,没有dp[1][2],因为根节点没有父亲
    return 0;
    }

  • 1
    @ 2018-02-23 20:35:52

    根节点没有父亲,因此取最小值只能去儿子和自己的

    树形DP+邻接表,没有用二叉链表结构,直接多叉树求解

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #define MAXN 1501
    #define INF 2100000000
    using namespace std;
    
    int n, c[MAXN];
    int from[MAXN], to[MAXN], first[MAXN], nxt[MAXN];
    int indeg[MAXN] = {0};
    int dp[MAXN][3] = {0};
    
    // 0->son, 1->self, 2->pa
    
    void dfs(int i){
        int e = first[i];
        int sonmin, selfmin, pamin, diffmin;
        diffmin = INF;
        while(e){
            dfs(to[e]);
            sonmin = selfmin = pamin = INF;
            selfmin = min(selfmin, dp[to[e]][0]);
            selfmin = min(selfmin, dp[to[e]][1]);
            selfmin = min(selfmin, dp[to[e]][2]);
            dp[i][1] += selfmin;
            sonmin = min(sonmin, dp[to[e]][0]);
            sonmin = min(sonmin, dp[to[e]][1]);
            diffmin = min(diffmin, dp[to[e]][1]-sonmin);
            dp[i][0] += sonmin;
            dp[i][2] += sonmin;
            e = nxt[e];
        }
        dp[i][0] += diffmin;
        dp[i][1] += c[i];
        // cout << endl << i << " : " << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
        return;
    }
    
    int main(){
        int ti, tn, tto, mcnt = 0, t;
        cin >> n;
        for(int i=0; i<n; i++){
            cin >> ti;
            cin >> c[ti];
            cin >> tn;
            for(int j=0; j<tn; j++){
                mcnt ++;
                cin >> tto;
                from[mcnt] = ti;
                to[mcnt] = tto;
                t = first[ti];
                first[ti] = mcnt;
                nxt[mcnt] = t;
                indeg[tto]++;
            }
        }
        int gans = 0;
        for(int i=1; i<=n; i++){
            if(!indeg[i]){
                memset(dp, 0, sizeof(dp));
                dfs(i);
                gans += min(dp[i][0], dp[i][1]);
            }
        }
        cout << gans << endl;
    
        return 0;
    }
    

    评测情况

     Accepted
    #   状态  耗时  内存占用
    #1  Accepted    3ms     340.0 KiB
    #2  Accepted    3ms     372.0 KiB
    #3  Accepted    4ms     356.0 KiB
    #4  Accepted    4ms     504.0 KiB
    #5  Accepted    7ms     352.0 KiB
    #6  Accepted    6ms     376.0 KiB
    #7  Accepted    3ms     352.0 KiB
    
  • 1
    @ 2016-11-04 15:52:36

    dp................
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <algorithm>
    using namespace std;
    const int N=1505;
    int n,a[N],nums[N],son[N][N],f[N][3];
    bool v[N];

    void dp(int root)
    {
    int tmp;
    if(nums[root]==0) return;
    for(int i=1;i<=nums[root];i++) dp(son[root][i]);
    tmp=1000000;
    for(int i=1;i<=nums[root];i++)
    {
    f[root][0]=f[root][0]+min(min(f[son[root][i]][0],f[son[root][i]][1]),f[son[root][i]][2]);
    f[root][1]=f[root][1]+min(f[son[root][i]][0],f[son[root][i]][1]);
    if(f[son[root][i]][0]-min(f[son[root][i]][0],f[son[root][i]][1])<tmp)
    tmp=f[son[root][i]][0]-min(f[son[root][i]][0],f[son[root][i]][1]);
    f[root][2]=f[root][2]+f[son[root][i]][1];
    }
    f[root][0]=f[root][0]+a[root];
    f[root][1]=f[root][1]+tmp;
    }

    int main()
    {
    //freopen("guard.in","r",stdin);
    //freopen("guard.out","w",stdout);
    int x,d,k,root;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d%d%d",&x,&d,&k);
    a[x]=d;
    nums[x]=k;
    for(int j=1;j<=k;j++)
    {
    scanf("%d",&son[x][j]);
    v[son[x][j]]=1;
    }
    }
    for(int i=1;i<=n;i++)
    if(!v[i])
    {
    root=i;
    break;
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    if(nums[i]==0)
    {
    f[i][0]=a[i];
    f[i][1]=1000000;
    f[i][2]=0;
    }
    dp(root);
    cout<<min(f[root][0],f[root][1])<<endl;
    //fclose(stdin);
    //fclose(stdout);
    return 0;
    }

  • 1
    @ 2016-09-29 06:58:34
    #include <cstdio>
    #include <cstdlib>
    #define maxn 1510
    typedef struct node
    {
                    int v;
                    struct node *next;
    }poi;
    
    int n,father[maxn],a[maxn],root,f[3][maxn];
    poi *l[maxn],*r[maxn];
    
    poi *newnode()
    {
                    poi *u=(poi*) malloc(sizeof(poi));
                    u->next=NULL;
                    return u;
    }
    
    void input_data()
    {
                    scanf("%d",&n);
                    for (int i=1;i<=n;i++)
                                    l[i]=r[i]=newnode(),father[i]=i;
                    for (int i=1;i<=n;i++)
                                    {
                                                    int x,y,w,num;
                                                    scanf("%d%d%d",&x,&w,&num);
                                                    a[x]=w;
                                                    for (int j=1;j<=num;j++)
                                                                    {
                                                                                    scanf("%d",&y);
                                                                                    r[x]=r[x]->next=newnode();
                                                                                    r[x]->v=y;
                                                                                    father[y]=x;
                                                                    }
                                    }
    }
    
    int search_father(int x)
    {
                    if (father[x] !=x)
                                    return (search_father(father[x]));
                                                    else return x;
    }
    
    int min(int a,int b)
    {
                    return a>b?b:a;
    }
    /*
                    f[0][x] 表示以x为根的子树已经被控制好,且x也被控制好,x放守卫。
                    f[1][x] 表示以x为根的子树已经被控制好,且x也被控制好,x不放守卫。
                    f[2][x] 表示以x为根的子树已经被控制好,但x没有被控制,且x不放守卫。
                    f[0][x]=∑min{f[0][y],f[1][y],f[2][y]}+a[x]; (y是x的直系儿子节点)
                    f[1][x]=∑min{f[0][y],f[1][y]}+(f[0][u]-f[1][u]);右半部分括号内的东西在y全都不放守卫时起作用。且(f[0][u]-f[1][u])min;
                    f[2][x]=∑f[1][y];
    */
    void cm(int x)
    {
                    poi *p=l[x]->next;
                    bool bo=false;
                    int special=10000;
                    while (p!=NULL)
                                    {
                                                    int y=p->v;
                                                    if (y!=x)
                                                                    {
                                                                                    cm(y);
                                                                                    f[0][x]+=min(f[0][y],min(f[1][y],f[2][y]));
                                                                                    if (f[0][y]<=f[1][y]) bo=true;
                                                                                    if (special>f[0][y]-f[1][y]) special=f[0][y]-f[1][y];
                                                                                    f[1][x]+=min(f[0][y],f[1][y]);
                                                                                    f[2][x]+=f[1][y];
                                                                    }
                                                    p=p->next;
                                    }
                    if (!bo) f[1][x]+=special;
                    f[0][x]+=a[x];
    }
    
    int main()
    {
                    input_data();
                    root=search_father(n);
                    cm(root);
                    printf("%d\n",min(f[1][root],f[0][root]));
                    return 0;
    }
    
  • 1
    @ 2016-06-29 18:04:18

    为了练习左子右兄法叫了好多次才发现错在哪里。。。
    果然还是太弱了。。。
    下面是核心:
    void dp(int x)
    {
    if(x==0)return ;
    int l=ch[x][0],r=ch[x][1];
    dp(l);dp(r);
    f[x][0][0]=f[l][1][0]+min(f[r][0][0],f[r][1][0]);
    f[x][1][0]=min(f[l][1][0]+f[r][1][0] , min(f[l][1][1],f[l][0][1])+min(f[r][0][0],f[r][1][0])+v[x]);
    f[x][0][1]=min(f[l][1][0],f[l][0][0])+min(f[r][0][1],f[r][1][1]);
    f[x][1][1]=min(min(f[l][1][0],f[l][0][0])+f[r][1][1] , min(f[l][1][1],f[l][0][1])+min(f[r][0][1],f[r][1][1])+v[x]);
    }

    • @ 2016-08-13 20:25:40

      树规从不用左子右兄的路过。。

  • 1
    @ 2016-03-13 15:54:41

    不知道为什么一直过不了,希望能够帮忙看一下。
    写的不算很丑,希望能认真的看一下。
    thanks~
    pascal
    var
    f:array[0..1500,0..2] of longint;
    a:array[0..1500,0..1500] of longint;
    w:array[0..1500] of longint;
    n,i,j,k,m,x,root:longint;
    function min(a,b:longint):longint;
    begin
    if a=0 then min:=b
    else if b=0 then min:=a
    else if a<b then min:=a
    else min:=b;
    end;
    procedure dp(u:longint);
    var
    mm,i,v:longint;
    begin
    f[u,0]:=w[u]; mm:=maxlongint;
    if a[u,0]=0 then exit;
    for i:=1 to a[u,0] do
    begin
    v:=a[u,i];
    dp(v);
    f[u,0]:=f[u,0]+min(f[v,0],min(f[v,1],f[v,2]));
    f[u,1]:=f[u,1]+min(f[v,0],f[v,1]);
    f[u,2]:=f[u,2]+f[v,1];
    mm:=min(mm,f[v,0]-f[v,1]);
    end;
    if mm>0 then f[u,1]:=f[u,1]+mm;
    end;
    begin
    readln(n); root:=0;
    for i:=1 to n do
    begin
    root:=root+i;
    read(k,w[k],m);
    for j:=1 to m do
    begin
    read(x);
    inc(a[k,0]);
    a[k,a[k,0]]:=x;
    root:=root-x;
    end;
    readln;
    end;
    dp(root);
    writeln(min(f[root,0],f[root,1]));
    end.

  • 0
    @ 2019-11-26 17:02:00

    看到各位dalao都用了dfs,嵌套循环的我瑟瑟发抖
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<queue>
    using namespace std;
    struct line
    {
    int to,ne;
    }st[1500];
    long long a[1501],dp[1501][3];
    int n,p,no,h[1501],s[1501],f[1501],vis[1501],ss[1501];
    void add(int x,int y)
    {
    st[++p].to=y;
    st[p].ne=h[x];
    h[x]=p;
    }
    int main()
    {

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&no);
    scanf("%lld%d",&a[no],&s[no]);
    ss[no]=s[no];
    for(int j=1;j<=s[no];j++)
    {
    int x;
    scanf("%d",&x);
    add(no,x);
    vis[x]=1;
    f[x]=no;
    }
    }
    for(int i=1;i<=n;i++)
    {
    if(!vis[i])
    {
    f[i]=0;
    memset(vis,0,sizeof(vis));
    break;
    }
    }
    for(int j=1;j<=n;j++)
    {
    if(!ss[j])
    {
    dp[j][1]=a[j];
    dp[j][0]=1e15+10;
    dp[j][2]=0;
    ss[f[j]]--;
    vis[f[j]]=1;
    ss[j]--;
    }
    }
    for(int i=1;i<=n;i++)
    {
    memset(vis,0,sizeof(vis));
    for(int j=1;j<=n;j++)
    {
    if(f[j]==0&&ss[j]==-1)
    {
    printf("%lld",min(dp[j][0],dp[j][1]));
    return 0;
    }
    if(ss[j]==0&&vis[j]==0)
    {
    int yes=1;
    if(h[j]!=0)
    yes=0;
    for(int ii=h[j];ii;ii=st[ii].ne)
    {
    if(dp[st[ii].to][1]<=dp[st[ii].to][0])
    yes=1;
    dp[j][2]+=min(dp[st[ii].to][0],dp[st[ii].to][1]);
    dp[j][1]+=min(dp[st[ii].to][0],min(dp[st[ii].to][1],dp[st[ii].to][2]));
    }
    dp[j][1]+=a[j];
    dp[j][0]=dp[j][2];
    if(!yes)
    {
    long long mi=1e15+10;
    for(int ii=h[j];ii;ii=st[ii].ne)
    {
    mi=min(mi,dp[st[ii].to][1]-dp[st[ii].to][0]);
    }
    dp[j][0]+=mi;
    }
    ss[f[j]]--;
    vis[f[j]]=1;
    ss[j]--;

    }
    }
    }
    return 0;
    }
    ```

  • 0
    @ 2017-09-22 20:27:28
    #include <stdio.h>
    using namespace std;
    int n;
    struct node
    {
        int fa;
        long long value;
        int childs;
        int child[1501];
    };
    node tree[1501];
    long long f[1501][4];
    int visited[1501];
    int t[1501];
    int root;
    int abs(int a)
    {
        if (a<0)
        return -a;
        else return a;
    }
    int min(int a,int b)
    {
        if (a<b)
        return a;
        else return b;
    }
    void dp(int now)
    {
        if (visited[now]==1||tree[now].childs==0) return;
        visited[now]=1;
        for (int i=1;i<=tree[now].childs;i++)
        dp(tree[now].child[i]);
        int temp=0;
        f[now][1]=tree[now].value;
        int minn=1000000;
        for (int i=1;i<=tree[now].childs;i++)
        {
            f[now][3]=f[now][3]+f[tree[now].child[i]][2];
            f[now][1]=f[now][1]+min(min(f[tree[now].child[i]][1],f[tree[now].child[i]][2]),f[tree[now].child[i]][3]);
            if (f[tree[now].child[i]][1]<=f[tree[now].child[i]][2])
            {
                temp=1;
                f[now][2]=f[now][2]+f[tree[now].child[i]][1];
            }
            else f[now][2]=f[now][2]+f[tree[now].child[i]][2];
            minn=min(minn,abs(f[tree[now].child[i]][1]-f[tree[now].child[i]][2]));
        }
        if (temp==0)
        f[now][2]=f[now][2]+minn;
    }
    int main()
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            int t1,t2,t3;
            scanf("%d%d%d",&t1,&t2,&t3);
            tree[t1].value=t2;
            tree[t1].childs=t3;
            for (int j=1;j<=t3;j++)
            {
                int temp;
            scanf("%d",&temp);
            tree[temp].fa=i;
            tree[t1].child[j]=temp;
            t[temp]=1;
            }
        }
        for (int i=1;i<=n;i++)
        if (t[i]==0)
        root=i;
        for (int i=1;i<=n;i++)
        if (tree[i].childs==0)
        {
            f[i][1]=tree[i].value;
            f[i][2]=10000000;
            f[i][3]=0;
        }
        dp(root);
        printf("%d\n",min(f[root][1],f[root][2]));
    
        return 0;
    }
    
  • 0
    @ 2017-09-15 08:23:02
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define fo(i,a,b) for(int i=a;i<=b;i++)
    #define fod(i,a,b) for(int i=a;i>=b;i--)
    using namespace std;
    const int N=1500+10;
    typedef long long ll;
    int last[N],n,len;
    ll dp1[N],dp2[N],dp3[N],w[N];
    
    struct Edge{int to,next;Edge(int to=0,int next=0):to(to),next(next){}}e[N<<1];
    void add_edge(int u,int v){e[++len]=Edge(v,last[u]);last[u]=len;}
    void dp(int x,int fa)
    {
        ll mn=(1<<30);
        dp1[x]=dp2[x]=dp3[x]=0;
        for(int i=last[x];i;i=e[i].next)
        {
            int id=e[i].to;
            if(id==fa)continue;
            dp(id,x);
            dp1[x]+=min(dp1[id],min(dp2[id],dp3[id]));
            dp2[x]+=min(dp1[id],dp2[id]);
            ll t=dp1[id]-min(dp1[id],dp2[id]);
            mn=min(mn,t);
            dp3[x]+=min(dp1[id],dp2[id]);
        }
        dp2[x]+=mn;dp1[x]+=w[x];
    }
    int main()
    {
        memset(dp1,127,sizeof(dp1));
        memset(dp2,127,sizeof(dp2));
        memset(dp3,127,sizeof(dp3));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int cur,K,num,son;
            scanf("%d%d%d",&cur,&K,&num);
            w[cur]=K;
            while(num--){scanf("%d",&son);add_edge(cur,son);add_edge(son,cur);}
        }
        dp(1,0);
        printf("%lld\n",min(dp1[1],dp2[1]));
        return 0;
    }       
    
  • 0
    @ 2017-07-05 10:16:05

    /* z.s */
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    using namespace std;
    const int maxn=1505;
    int n;
    vector<int> q[maxn];
    int w[maxn];
    int f1[maxn],f2[maxn],f3[maxn];
    int f[maxn];
    int ans;
    void dfs(int rt)
    {
    int cnt=0x7f7f7f7f;
    for(int i=0;i<q[rt].size();i++)
    {
    int tmp=q[rt][i];
    dfs(tmp);
    f1[rt]+=min(f1[tmp],min(f2[tmp],f3[tmp]));
    f2[rt]+=min(f1[tmp],f2[tmp]);
    cnt=min(cnt,f1[tmp]-min(f1[tmp],f2[tmp]));
    f3[rt]+=min(f1[tmp],f2[tmp]);
    }
    f2[rt]+=cnt;
    f1[rt]+=w[rt];
    }
    int main()
    {
    scanf("%d",&n);
    for(int i=1,id,m;i<=n;i++)
    {
    scanf("%d",&id);
    scanf("%d%d",&w[id],&m);
    for(int j=1,r;j<=m;j++)
    {
    scanf("%d",&r);
    q[id].push_back(r);
    f[r]=id;
    }
    }
    for(int i=1;i<=n;i++)
    if(!f[i])
    {
    dfs(i);
    ans=min(f1[i],f2[i]);
    break;
    }
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2017-05-20 16:32:09
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    const int n_r=1500,oo_max=0x3f3f3f3f,oo_min=0xcfcfcfcf;
    
    struct v_1
    {
        int h,v;
        vector<int> s;
    }a[n_r+1];
    
    int n,t_h;
    int f[n_r+1][3];
    bool b[n_r+1];
    
    void work_1(int now)
    {
        int v_0=0,v_1=0,v_2=0,min_x_1=oo_max;
        for (int i=1;i<a[now].s.size();i++)
        {
            work_1(a[now].s[i]);
            min_x_1=min(min_x_1,f[a[now].s[i]][2]-f[a[now].s[i]][1]);
            v_0+=min(f[a[now].s[i]][1],f[a[now].s[i]][2]);
            v_1+=min(f[a[now].s[i]][1],f[a[now].s[i]][2]);
            v_2+=min(f[a[now].s[i]][0],min(f[a[now].s[i]][1],f[a[now].s[i]][2]));
        }
        v_1+=(min_x_1>0)?min_x_1:0;
        v_2+=a[now].v;
        f[now][0]=min(f[now][0],v_0);
        f[now][1]=min(f[now][1],v_1);
        f[now][2]=min(f[now][2],v_2);
    }
    
    int main()
    {
        while (~scanf("%d",&n))
        {
            memset(b,0,sizeof(b));
            for (int i=1;i<=n;i++)
            {
                int now,m;
                scanf("%d",&now);
                scanf("%d",&a[now].v);
                scanf("%d",&m);
                a[now].s.resize(m+1,0);
                for (int j=1;j<=m;j++)
                {
                    scanf("%d",&a[now].s[j]);
                    b[a[now].s[j]]=1;
                }
            }
            for (int i=1;i<=n;i++)
                if (b[i]==0)
                {
                    t_h=i;
                    break;
                }
            memset(f,oo_max,sizeof(f));
            work_1(t_h);
            printf("%d\n",min(f[t_h][1],f[t_h][2]));
        }
    }
    
  • 0
    @ 2017-04-05 22:15:38
  • 0
    @ 2016-06-29 18:04:56

    补充:
    f[0][0][0]=f[0][0][1]=0;
    f[0][1][0]=f[0][1][1]=INF;

  • 0
    @ 2015-10-10 19:20:19

    #include <cstdio>
    #include <algorithm>
    const int size=1505;
    int n,m,x,i,j;
    int son[size][size];
    int tot[size],cost[size],flag[size];
    int f[size][3];//0表示未被自己或儿子覆盖 1表示自己覆盖 2表示被儿子覆盖
    using namespace std;
    void init()
    {
    //freopen("palace.in","r",stdin);
    //freopen("palace.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    f[i][1]=f[i][2]=1431655;
    for (i=1;i<=n;i++)
    {
    scanf("%d",&x);
    scanf("%d%d",&cost[x],&m);
    for (j=1;j<=m;j++)
    {
    int p=++tot[x];
    scanf("%d",&son[x][p]);
    flag[son[x][p]]=1;//标识为1
    }
    }
    }
    void DP(int k)
    {
    f[k][1]=cost[k];
    if (tot[k]==0) return;
    for (int i=1;i<=tot[k];i++)
    DP(son[k][i]);//往下枚举

    //用儿子更新自己的值
    for (int i=1;i<=tot[k];i++)
    {
    int temp=son[k][i];
    f[k][1]+=min(f[temp][0],min(f[temp][1],f[temp][2]));
    }//自己覆盖,儿子随便怎么样都可以

    for (int i=1;i<=tot[k];i++)
    {
    int s=f[son[k][i]][1]; //自己覆盖的儿子的代价
    for (int j=1;j<=tot[k];j++)
    if (j!=i)
    {
    int temp=son[k][j];
    s+=min(f[temp][1],f[temp][2]);
    }
    f[k][2]=min(f[k][2],s);
    }//有一个儿子自己覆盖,其他随意(2/1),选一个最优值

    for (int i=1;i<=tot[k];i++)
    f[k][0]+=f[son[k][i]][2];//自己的儿子被孙子覆盖,但自己未被覆盖
    }
    int main()
    {
    init();
    for (i=1;i<=n;i++)
    if (flag[i]==0) //如果标识为0,就是树根
    {
    DP(i);
    printf("%d\n",min(f[i][1],f[i][2]));
    break;
    }
    return 0;
    }

    • @ 2015-10-10 19:22:52

      一开始WA的原因是初始化的数太大了
      如果求所有儿子的和会超过int范围,然后负数影响了最优值的正确性。
      把2147483647/1500赋给每个点就AC了。
      头一次写树形DP写A了,真是心情舒畅

  • 0
    @ 2015-10-07 12:09:40

    其实我写这道题的时候还不怎么了解<树形DP>,思路不很明朗,wrong answer了很多次……
    ###QAQ

    ###不过那些0s的是咋搞的?
    记录信息
    评测状态 Accepted
    题目 P1144 小胖守皇宫
    递交时间 2015-10-07 11:54:53
    代码语言 C++
    评测机 VijosEx
    消耗时间 24 ms
    消耗内存 636 KiB
    评测时间 2015-10-07 11:54:54
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 1 ms, mem = 576 KiB, score = 14
    测试数据 #1: Accepted, time = 1 ms, mem = 576 KiB, score = 14
    测试数据 #2: Accepted, time = 1 ms, mem = 576 KiB, score = 14
    测试数据 #3: Accepted, time = 1 ms, mem = 636 KiB, score = 14
    测试数据 #4: Accepted, time = 8 ms, mem = 580 KiB, score = 14
    测试数据 #5: Accepted, time = 6 ms, mem = 580 KiB, score = 14
    测试数据 #6: Accepted, time = 6 ms, mem = 576 KiB, score = 14
    Accepted, time = 24 ms, mem = 636 KiB, score = 98

    ###代码
    #include <iostream>
    #include <stdio.h>
    using namespace std;
    const int inf=2100000000;
    int fir[1510];
    int nxt[3020];
    int link[3020];
    int dp[1510][3];
    /*dp[now][0]表示now点不安置守卫的最低花费,而是通过其子节点的守卫守卫,dp[now][1]表示now点安置守卫的最低花费,dp[now][2]表示now点不安置守卫,而是通过其父节点的守卫守卫的最低花费*/
    int cost[1510]; //每个点的花费
    int cnt;
    void Link(int a,int b){nxt[++cnt]=fir[a];link[cnt]=b;fir[a]=cnt;}
    void search(int now,int pre)
    {
    dp[now][1]=cost[now];
    dp[now][2]=0;
    int flag=inf;
    for(int i=fir[now];i;i=nxt[i])
    {
    if(link[i]!=pre){
    search(link[i],now);//先向下走,再从下往上DP

    dp[now][0]+=min(dp[link[i]][1],dp[link[i]][0]);
    dp[now][1]+=min(dp[link[i]][1],min(dp[link[i]][2],dp[link[i]][0]));
    dp[now][2]+=min(dp[link[i]][0],dp[link[i]][1]);

    //DP

    if(dp[link[i]][1]<=dp[link[i]][0])flag=0;
    if(flag&&dp[link[i]][1]-dp[link[i]][0]<flag){
    flag=dp[link[i]][1]-dp[link[i]][0];
    }
    //特判,由于dp[now][0]只需要其某一个‘now的子节点’有守卫即可,需特殊处理
    }
    }

    dp[now][0]+=flag; //当now没有子节点时,dp[now][0]=inf;
    }
    int main()
    {
    int n;
    scanf("%d",&n);
    while(n--)
    {
    int a,b,k;
    scanf("%d",&a);
    scanf("%d",&cost[a]);
    scanf("%d",&k);
    while(k--){
    scanf("%d",&b);
    Link(a,b);
    Link(b,a);
    }
    }
    search(1,0);
    printf("%d",min(dp[1][0],dp[1][1]));
    }

  • 0
    @ 2015-09-18 13:38:51

    var son:array[0..1500,0..1500] of longint;
    a:array[0..1500,0..2] of longint;
    w,fa:array[0..1500] of longint;
    n,m,i,j,k,l:longint;
    function min(x,y,z:longint):longint;
    begin
    if x<=y then
    if x<=z then exit(x);
    if y<=x then
    if y<=z then exit(y);
    if z<=x then
    if z<=y then exit(z);
    end;
    procedure dp(i:longint);
    var r,o,l,m:longint;
    begin
    if son[i,0]=0 then begin a[i,1]:=w[i]; a[i,0]:=w[i]; exit; end;
    for r:=1 to son[i,0] do
    dp(son[i,r]);
    a[i,1]:=w[i];
    for r:=1 to son[i,0] do
    a[i,1]:=a[i,1]+min(a[son[i,r],0],a[son[i,r],1],a[son[i,r],2]);
    for r:=1 to son[i,0] do
    a[i,2]:=a[i,2]+min(a[son[i,r],0],a[son[i,r],1],maxlongint);
    m:=0; l:=maxlongint;
    for r:=1 to son[i,0] do
    if a[son[i,r],1]-a[son[i,r],0]<l then
    begin
    l:=a[son[i,r],1]-a[son[i,r],0];
    m:=son[i,r];
    end;
    for r:=1 to son[i,0] do
    if son[i,r]<>m then
    a[i,0]:=a[i,0]+min(a[son[i,r],1],a[son[i,r],0],maxlongint)
    else
    a[i,0]:=a[i,0]+a[son[i,r],1];
    end;
    begin
    read(n);
    for i:=1 to n do
    begin
    read(j,w[j],m); son[j,0]:=m;
    for l:=1 to m do
    begin
    read(son[j,l]);
    fa[son[j,l]]:=j;
    end;
    end;
    j:=1;
    while fa[j]<>0 do
    j:=fa[j];
    dp(j);
    writeln(min(maxlongint,a[j,0],a[j,1]));

    end.
    我想说DP思维都是很重要的,一开始错了,就难做了。

  • 0
    @ 2015-08-15 20:16:00

    记录信息
    评测状态 Accepted
    题目 P1144 小胖守皇宫
    递交时间 2015-08-15 20:06:13
    代码语言 Pascal
    评测机 VijosEx
    消耗时间 0 ms
    消耗内存 840 KiB
    评测时间 2015-08-15 20:06:13
    评测结果
    编译成功

    Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
    Copyright (c) 1993-2014 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    Linking foo.exe
    120 lines compiled, 0.1 sec , 29456 bytes code, 1628 bytes data
    测试数据 #0: Accepted, time = 0 ms, mem = 800 KiB, score = 14
    测试数据 #1: Accepted, time = 0 ms, mem = 800 KiB, score = 14
    测试数据 #2: Accepted, time = 0 ms, mem = 796 KiB, score = 14
    测试数据 #3: Accepted, time = 0 ms, mem = 840 KiB, score = 14
    测试数据 #4: Accepted, time = 0 ms, mem = 796 KiB, score = 14
    测试数据 #5: Accepted, time = 0 ms, mem = 796 KiB, score = 14
    测试数据 #6: Accepted, time = 0 ms, mem = 796 KiB, score = 14
    Accepted, time = 0 ms, mem = 840 KiB, score = 98
    代码
    program P1144;
    type
    tNode=record
    num:integer;
    first,last:integer;
    cost:integer;
    end;

    var
    size:integer;
    child:array[1..1500] of integer;
    node:array[1..1500] of tNode;
    loc:array[1..1500] of integer;
    answer:array[1..1500,0..2] of longint;
    i,j,k,top,temp:integer;
    function getRoot:integer;
    var
    i:integer;
    flag:array[1..1500] of boolean;
    begin
    for i:=1 to top do
    begin
    flag[i]:=true;
    end;
    for i:=1 to top do
    begin
    flag[child[i]]:=false;
    end;
    for i:=1 to top do
    begin
    if flag[i] then
    begin
    exit(loc[i]);
    end;
    end;
    end;
    function min(a,b:longint):longint;
    begin
    if a<b then
    begin
    exit(a);
    end;
    exit(b);
    end;

    function dp(this,flag:integer):longint;
    var
    i:integer;
    sum:longint;
    begin
    if answer[this,flag]>=0 then
    begin
    exit(answer[this,flag]);
    end;
    if node[this].last<node[this].first then
    begin
    if flag<>0 then
    begin
    answer[this,flag]:=node[this].cost;
    end
    else
    begin
    answer[this,flag]:=0;
    end;
    exit(answer[this,flag]);
    end;
    sum:=0;
    for i:=node[this].first to node[this].last do
    begin
    sum:=sum+dp(loc[child[i]],0);
    end;
    dp:=sum+node[this].cost;
    if flag<>2 then
    begin
    sum:=0;
    for i:=node[this].first to node[this].last do
    begin
    sum:=sum+dp(loc[child[i]],1);
    end;
    for i:=node[this].first to node[this].last do
    begin
    dp:=min(dp,sum-dp(loc[child[i]],1)+dp(loc[child[i]],2));
    end;
    end;
    if flag=0 then
    begin
    sum:=0;
    for i:=node[this].first to node[this].last do
    begin
    sum:=sum+dp(loc[child[i]],1);
    end;
    dp:=min(dp,sum);
    end;
    answer[this,flag]:=dp;
    end;
    begin
    top:=1;
    readln(size);
    for i:=1 to size do
    begin
    read(j);
    loc[j]:=i;
    node[i].num:=j;
    read(node[i].cost,j);
    node[i].first:=top;
    node[i].last:=top+j-1;
    for k:=top to top+j-1 do
    begin
    read(temp);
    child[k]:=temp;
    end;
    top:=top+j;
    end;
    for i:=1 to size do
    begin
    answer[i,0]:=-1;
    answer[i,1]:=-1;
    answer[i,2]:=-1;
    end;
    writeln(DP(getRoot,1));
    end.

    另answer[i,0]表示i号节点被他爸罩着,这个子树的最少花费,answer[i,1]表示第i个节点不被他爸罩着,他爸也不要求他罩的最少花费。answer[i,2]表示这个节点需要罩着他爸的最小花费。那么

    answer[i,0]=求和(answer[i的子树,1])
    answer[i,1]=min(求和(answer[i的大部分子树,0])+answer[i剩下一个子树,2],求和(answer[i的子树,0])+cost[i]);
    answer[i,2]=cost[i]+求和(answer[i的子树,0])

  • 0
    @ 2014-10-17 21:30:15

    树形DP
    dp(x,flag,flag)表示标号为x的节点是否选,而且他是否被父亲或自己看住。
    dp(x,1,1)=Σmin(dp(ch[x][i],1,1),dp(ch[x][i],0,1));
    dp(x,0,1)=Σmin(dp(ch[x][i],1,1),dp(ch[x][i],0,0));
    dp(x,0,0)的转移复杂一点:从儿子中找出dp(ch[x][i],0,0)-dp(ch[x][t],1,1)最大的点,选中他来看住父亲,
    dp(x,0,0)=dp(ch[x][t],1,1)+Σmin(dp(ch[x][i],0,0),dp(ch[x][i],1,1))(i!=t);(在此种情况下某种节点没有孩子,便返回INF)

信息

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