/ Vijos / 题库 / 舞会 /

题解

25 条题解

  • 2
    @ 2019-06-27 22:13:26
    //此题为没有上司的舞会的弱化版,有需要可以移步
    //是比较简单的树状DP了
    #include<iostream>
    #include<vector>
    using namespace std;
    int dp[5010][2];
    vector<int> q[5010];
    void dfs(int u,int v)
    {
        int d=q[u].size(),i;
        for(i=0;i<d;i++)
         {
            dfs(q[u][i],u);
            dp[u][0]+=max(dp[q[u][i]][0],dp[q[u][i]][1]);
            dp[u][1]+=dp[q[u][i]][0];
         }
        return ;
    }
    int main()
    {
        int n,i,t;
        cin>>n;
        for(i=1;i<=n;i++)
         cin>>dp[i][1];
        for(i=2;i<=n;i++)
        {
            cin>>t;
            q[t].push_back(i);
        }
        dfs(1,1);
        cout<<max(dp[1][1],dp[1][0]);
        return 0;
    }
    
  • 2
    @ 2017-01-30 14:45:28
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int n,f[5001][2];
    
    struct node1
    {
        int a,h,sn,s[5001];
    }a[5001];
    
    void dfs1(int x)
    {
        int v1=0,v2=0;
        for (int i=1;i<=a[x].sn;i++)
        {
            dfs1(a[x].s[i]);
            v1+=max(f[a[x].s[i]][0],f[a[x].s[i]][1]);
            v2+=max(f[a[x].s[i]][0],0);
        }
        f[x][0]=max(f[x][0],v1);
        f[x][1]=max(f[x][1],a[x].a+v2);
    }
    
    int main()
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            a[i].sn=0;
            memset(a[i].s,0,sizeof(a[i].s));
        }
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i].a);
        a[0].h=a[1].h=0;
        a[0].s[++a[0].sn]=1;
        for (int i=2;i<=n;i++)
        {
            scanf("%d",&a[i].h);
            a[a[i].h].s[++a[a[i].h].sn]=i;
        }
        memset(f,0,sizeof(f));
        dfs1(0);
        printf("%d\n",f[0][0]);
    }
    
  • 1
    @ 2018-07-19 15:19:17

    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    #define MAXN 6005
    int v[MAXN];
    int h[MAXN];
    int f[MAXN][2];
    vector <int> son[MAXN];//本题唯一STL
    void DP(int x)
    {
    f[x][0]=0;//基本定义条件
    f[x][1]=h[x];
    for(int i=0;i<son[x].size();i++)//这里调用了vector库,STL大法好
    {
    int y=son[x][i];//STL就是方便
    DP(y);//递归算法好
    f[x][0]+=max(f[y][1],f[y][0]);//建立DP方程
    f[x][1]+=f[y][0];//建立DP方程
    }
    }
    int main()
    {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>h[i];}
    for(int i=2;i<=n;i++)
    {
    int y;
    cin>>y;
    son[y].push_back(i);//STL
    v[i]=i;//其实这里完全没有必要
    }

    int root;
    for(int i=1;i<=n;i++)
    {
    if(!v[i])//这个判断对应上面,其实完全可以去root=1,这样的话更灵活一些
    {
    root =i;
    break;
    }
    }
    DP(root);
    cout<<max(f[root][0],f[root][1]);//输出最老的父亲的最大值
    }

  • 0
    @ 2018-03-15 07:36:07

    建树,dfs一次,转移是下标0不选,下标1选.转移方程如下.

    #include<bits/stdc++.h>
    int read(){int x=0,f=1;char c=getchar();for (;!isdigit(c);c=getchar()) f^=c=='-';for (;isdigit(c);c=getchar()) x=x*10+c-'0';return x*(f?1:-1);}
    int write(int x){if (!x) return putchar(48);if (x<0) putchar('-'),x=-x;register int bit[20],p=0,i;for (;x;x/=10) bit[++p]=x%10;for (i=p;i;--i) putchar(bit[i]+48);}
    using namespace std;
    int n=read(),dp[6666][2],ans;
    vector<int> lj[6666];
    
    void dfs(int u)
    {
    for (int i:lj[u]) 
      {
      dfs(i);
      dp[u][1]+=dp[i][0];
      dp[u][0]+=max(dp[i][1],dp[i][0]);
      ans=max(ans,max(dp[u][0],dp[u][1]));
      }
    }
    
    int main()
    {
    int i;
    for (i=1;i<=n;++i) dp[i][1]=read();
    ans=dp[1][1];
    for (i=2;i<=n;++i) 
      {
      int k=read();
      lj[k].push_back(i);
      }
    dfs(1);
    write(ans);
    }
    
  • 0
    @ 2017-10-21 14:27:04

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=5001;
    inline int init(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
    struct node{int lef,rig,val;}tree[maxn];
    int n,fa[maxn],pos[maxn],ex[maxn][3000];
    void readE(){
    n=init();
    for(int i=1;i<=n;i++)tree[i].val=init();
    for(int i=1;i<n;i++)fa[i]=init();
    for(int i=1;i<n;i++){
    if(!pos[fa[i]])tree[fa[i]].lef=i+1;
    else tree[pos[fa[i]]].rig=i+1;//儿子在左,兄弟在右
    pos[fa[i]]=i+1;
    }
    }
    int dpE(int r,int w){
    if(ex[r][w])return ex[r][w];
    int sum=0,pos;
    if(w){//要自己,儿子不能来,兄弟可来可不来
    pos=tree[r].lef;
    while(pos)sum+=dpE(pos,0),pos=tree[pos].rig;
    return ex[r][w]=sum+tree[r].val;
    }
    else {//不要自己,儿子可以来,兄弟也可以来
    pos=tree[r].lef;
    while(pos)sum+=max(dpE(pos,0),dpE(pos,1)),pos=tree[pos].rig;
    return ex[r][w]=sum;
    }
    }
    int main(){
    readE();
    printf("%d\n",max(dpE(1,0),dpE(1,1)));
    return 0;
    }
    注释给的应该很清楚了,不懂的可以问,但我不一定会马上回

  • 0
    @ 2017-05-28 22:36:48

    dfs

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 5005;
    int n, f[N], g[N], a[N], head[N], m;
    struct edge {int to, next;} e[N];
    void addedge (int u, int v) {e[++m] = (edge){v, head[u]}; head[u] = m;}
    void dfs (int x) {
        for (int i = head[x]; i; i = e[i].next) {
            dfs (e[i].to);
            f[x] += max (g[e[i].to], 0);
            g[x] += max (f[e[i].to], g[e[i].to]);
        }
    }
    int main () {
        int fa; scanf ("%d", &n);
        for (int i = 1; i <= n; ++ i) {
            scanf ("%d", &a[i]); f[i] = a[i];
        }
        for (int i = 2; i <= n; ++ i) {
            scanf ("%d", &fa); addedge (fa, i);
        } dfs (1); printf ("%d\n", max (f[1], g[1]));
        return 0;
    }
    

    bfs

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 5005;
    
    //----------------------------------------------------------------------
    
    struct Queue {
        int seq[N], front, tail, size;
        void Clear () {
            memset (seq, 0, sizeof(seq));
            front = 1, tail = 0, size = 0;
        }
        void Push (int x) {
            if (tail == N) {seq[1] = x; tail = 1;}
            else seq[++ tail] = x;
            ++ size;
        }
        void Pop () {
            if (front == N) front = 1; else ++ front;
            -- size;
        }
        int Front () {return seq[front];}
        bool Empty () {return !size;}
    };
    
    //----------------------------------------------------------------------
    
    int n, f[N], g[N], a[N], head[N], fa[N], m, rk[N], cnt;
    struct edge {int to, next;} e[N];
    Queue q;
    void addedge (int u, int v) {
        e[++m] = (edge){v, head[u]}; head[u] = m;
    }
    void bfs (int x) {
        q.Clear(); q.Push(x);
        while (!q.Empty()) {
            for (int i = head[q.Front()]; i; i = e[i].next)
                q.Push(e[i].to);
            rk[++cnt] = q.Front(); q.Pop();
        }
    }
    int main () {
        int ff; scanf ("%d", &n);
        for (int i = 1; i <= n; ++ i) {
            scanf ("%d", &a[i]); f[i] = a[i];
        }
        for (int i = 2; i <= n; ++ i) {
            scanf ("%d", &ff); addedge (ff, i);
            fa[i] = ff;
        } bfs (1);
        for (int i = n; i > 1; -- i) {
            int x = rk[i]; 
            f[fa[x]] += max (g[x], 0);
            g[fa[x]] += max (f[x], g[x]);
        }
        printf ("%d\n", max (f[1], g[1]));
        return 0;
    }
    

    其实这个顺序只要保证一个点的父亲在它的后面就行。。。

  • 0
    @ 2016-09-05 09:03:47

    // 树形DP
    {
    f[i][0]:表示选第i个节点
    f[i][1]:表示不选第i个节点

    f[i][0]:=v[i]+sum(f[j][0]);
    f[i][1]:=sum(max(f[j][0]+f[j][1]))
    }
    ```
    uses math;

    type
    re=record
    v,next:longint;
    end;

    var
    n,u,v,i,j,tot:longint;
    a,last:array[0..5000]of longint;
    f:array[0..5000,0..1]of longint;
    t:array[0..5000*2]of re;

    procedure add(u,v:longint);
    begin
    inc(tot);
    t[tot].v:=v;
    t[tot].next:=last[u];
    last[u]:=tot;
    end;

    procedure Init;
    var
    i,j:longint;
    begin
    readln(n);
    for i:=1 to n do
    begin
    read(a[i]);
    f[i][0]:=a[i];
    end;
    for i:=1 to n-1 do
    begin
    readln(u);
    add(u,i+1); add(i+1,u);
    end;
    end;

    procedure Dfs_Dp(i,fat:longint);
    var
    x,tox:longint;
    begin
    x:=last[i];
    while x<>0 do
    begin
    tox:=t[x].v;
    if tox<>fat then Dfs_Dp(tox,i);
    x:=t[x].next;
    end;
    f[fat][0]:=f[fat][0]+f[i][1];
    f[fat][1]:=f[fat][1]+max(f[i][1],f[i][0]);
    end;

    begin
    Init;
    Dfs_Dp(1,0);
    writeln(max(f[1][0],f[1][1]));
    end.
    ```

  • 0
    @ 2016-02-06 11:08:38

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;
    int dp[5020][2];
    int n;
    int val[5020];
    vector<int> node[5020];
    void dfs(int fa){
    dp[fa][0]=0;dp[fa][1]=val[fa];
    for (int i=0;i<node[fa].size();i++){
    int son=node[fa][i];
    dfs(son);
    dp[fa][1]+=dp[son][0];
    dp[fa][0]+=max(dp[son][0],dp[son][1]);
    }
    }
    int main()
    {
    memset(dp,0,sizeof(dp));
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&val[i]);
    for (int i=1;i<n;i++){
    int x;
    scanf("%d\n",&x);
    node[x].push_back(i+1);
    }
    dfs(1);
    printf("%d\n",max(dp[1][0],dp[1][1]));
    return 0;
    }

  • 0
    @ 2015-08-25 23:03:50

    P1706舞会
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1706 舞会
    递交时间 2015-08-25 23:03:19
    代码语言 C++
    评测机 VijosEx
    消耗时间 115 ms
    消耗内存 852 KiB
    评测时间 2015-08-25 23:03:20

    评测结果

    编译成功

    foo.cpp: In function 'int dp(int)':
    foo.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for( i = 0 ; i < s[x] -> son.size() ; i++ )
    ^
    foo.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for( i = 0 ; i < s[x] -> son.size() ; i++ )
    ^
    foo.cpp:32:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for( j = 0 ; j < s[ cur ] -> son.size() ; j++ )
    ^

    测试数据 #0: Accepted, time = 0 ms, mem = 528 KiB, score = 10

    测试数据 #1: Accepted, time = 1 ms, mem = 532 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 536 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 536 KiB, score = 10

    测试数据 #4: Accepted, time = 15 ms, mem = 724 KiB, score = 10

    测试数据 #5: Accepted, time = 15 ms, mem = 800 KiB, score = 10

    测试数据 #6: Accepted, time = 15 ms, mem = 600 KiB, score = 10

    测试数据 #7: Accepted, time = 34 ms, mem = 708 KiB, score = 10

    测试数据 #8: Accepted, time = 15 ms, mem = 852 KiB, score = 10

    测试数据 #9: Accepted, time = 20 ms, mem = 848 KiB, score = 10

    Accepted, time = 115 ms, mem = 852 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>
    #include <vector>

    using namespace std;

    struct Node
    {
    vector < int > son;
    int value;
    int sonsum;
    };

    int n;
    int i;
    Node * s[5000 + 2];

    int dp( int x )
    {
    if( s[x] -> son.size() == 0 )
    return max( s[x] -> value , 0 );
    if( s[x] -> sonsum != -1 )
    return s[x] -> sonsum;
    int i , j , cur;
    for( i = 0 ; i < s[x] -> son.size() ; i++ )
    s[x] -> sonsum += dp( s[x] -> son[i] );
    s[x] -> sonsum++;
    int temp = s[x] -> value;
    for( i = 0 ; i < s[x] -> son.size() ; i++ )
    {
    cur = s[x] -> son[i];
    for( j = 0 ; j < s[ cur ] -> son.size() ; j++ )
    temp += dp( s[ cur ] -> son[j] );
    }
    s[x] -> sonsum = max( s[x] -> sonsum , temp );
    return s[x] -> sonsum;
    }

    int root;
    int t;

    int main()
    {
    scanf( "%d" , &n );
    for( i = 1 ; i <= n ; i++ )
    {
    s[i] = new Node();
    s[i] -> sonsum = -1;
    scanf( "%d" , &s[i] -> value );
    }
    for( i = 2 ; i <= n ; i++ )
    {
    scanf( "%d" , &t );
    s[t] -> son.push_back( i );
    }
    root = 1;
    cout << dp( root ) << endl;
    return 0;
    }

  • 0
    @ 2015-03-06 23:14:16

    var
    tot,i,j,k,n,m,s,t,ans:longint;
    head,vet,next,a:array[0..5001]of longint;
    f:array[0..5001,0..1]of longint;
    p:array[0..5001]of boolean;
    function max(i,j:longint):longint;
    begin
    if i>j then exit(i);exit(j);
    end;
    procedure add(u,v:longint);
    begin
    inc(tot);
    vet[tot]:=v;
    next[tot]:=head[u];
    head[u]:=tot;
    end;
    procedure try(i:longint);
    var j,t,e:longint;
    begin
    if p[i] then exit;
    f[i,0]:=0;f[i,1]:=a[i];
    e:=head[i];
    while e<>-1 do
    begin
    j:=vet[e];
    try(j);t:=max(f[j,0],f[j,1]);
    if t<0 then t:=0;
    f[i,0]:=f[i,0]+t;
    f[i,1]:=f[i,1]+max(f[j,0],0);
    e:=next[e];
    end;
    p[i]:=true;
    end;
    begin
    readln(n);
    for i:=1 to n do read(a[i]);readln;
    for i:=1 to n do head[i]:=-1;
    for i:=2 to n do
    begin
    readln(k);
    add(k,i);
    end;
    fillchar(p,sizeof(p),false);
    try(1);
    writeln(max(f[1][0],f[1][1]));
    end.

  • 0
    @ 2014-08-21 23:18:07

    while (p1<>p2) do
    begin
    pp:=dep;
    f[pp,1]:=f[pp,1]+max(a[pp],0);
    if pp=1 then break;
    f[fa[pp],0]:=f[fa[pp],0]+max(f[pp,1],f[pp,0]);
    f[fa[pp],1]:=f[fa[pp],1]+f[pp,0];
    dec(d[fa[pp]]);if d[fa[pp]]=0 then join(fa[pp]);
    end;

  • 0
    @ 2014-08-16 15:45:48

    var

    a,fu,f:array[1..5002]of longint;

    opt:array[1..5002,0..1]of longint;

    n,i,j,ans:longint;

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

    begin

    if a>b then

    exit(a)

    else

    exit(b);

    end;

    procedure dfs(x:longint);

    var

    i,a1,a0:longint;

    begin

    if f[x]=0 then

    begin

    opt[x,0]:=0;

    opt[x,1]:=a[x];

    end

    else

    begin

    for i:=1 to n do

    if fu[i]=x then

    dfs(i);

    a0:=0;

    a1:=0;

    for i:=1 to n do

    if fu[i]=x then

    begin

    a0:=a0+max(opt[i,0],opt[i,1]);

    a1:=a1+opt[i,0];

    end;

    opt[x,0]:=a0;

    opt[x,1]:=a1+a[x];

    end;

    end;

    begin

    read(n);

    for i:=1 to n do

    read(a[i]);

    for i:=1 to n-1 do

    begin

    read(j);

    fu[i+1]:=j;

    f[j]:=1;

    end;

    dfs(1);

    ans:=max(opt[1,1],opt[1,0]);

    writeln(ans);

    end.

  • 0
    @ 2014-08-16 15:43:47

    var
    a,fu,f:array[1..5002]of longint;
    opt:array[1..5002,0..1]of longint;
    n,i,j,ans:longint;
    function max(a,b:longint):longint;
    begin
    if a>b then
    exit(a)
    else
    exit(b);
    end;
    procedure dfs(x:longint);
    var
    i,a1,a0:longint;
    begin
    if f[x]=0 then
    begin
    opt[x,0]:=0;
    opt[x,1]:=a[x];
    end
    else
    begin
    for i:=1 to n do
    if fu[i]=x then
    dfs(i);
    a0:=0;
    a1:=0;
    for i:=1 to n do
    if fu[i]=x then
    begin
    a0:=a0+max(opt[i,0],opt[i,1]);
    a1:=a1+opt[i,0];
    end;
    opt[x,0]:=a0;
    opt[x,1]:=a1+a[x];
    end;
    end;
    begin

    read(n);
    for i:=1 to n do
    read(a[i]);
    for i:=1 to n-1 do
    begin
    read(j);
    fu[i+1]:=j;
    f[j]:=1;
    end;
    dfs(1);
    ans:=max(opt[1,1],opt[1,0]);
    writeln(ans);
    end.

  • 0
    @ 2014-08-16 10:58:28

    var
    a:array[1..5000] of longint;
    opt:array[1..5000,0..1] of longint;
    fa,hh:array[1..5000] of longint;
    n:longint;
    function max(x,y:longint):longint;
    begin
    if x>y then exit(x);
    exit(y);
    end;
    procedure init;
    var
    i,k:longint;
    begin
    fillchar(opt,sizeof(opt),0);
    fillchar(hh,sizeof(hh),0);
    read(n);
    for i:=1 to n do
    read(a[i]);
    for i:=1 to n-1 do
    begin
    read(k);
    fa[i+1]:=k;
    hh[k]:=1;
    end;
    end;
    procedure dfs(x:longint);
    var
    i,ans0,ans1:longint;
    begin
    if hh[x]=0 then
    begin
    opt[x,0]:=0;
    opt[x,1]:=a[x];
    end
    else
    begin
    for i:=1 to n do
    if fa[i]=x then dfs(i);
    ans0:=0;
    ans1:=0;
    for i:=1 to n do
    if fa[i]=x then
    begin
    ans0:=ans0+max(opt[i,0],opt[i,1]);
    ans1:=ans1+opt[i,0];
    end;
    opt[x,1]:=ans1+a[x];
    opt[x,0]:=ans0;
    end;
    end;
    procedure print;
    var
    ans:longint;
    begin
    ans:=max(opt[1,1],opt[1,0]);
    writeln(ans);
    end;
    begin
    init;
    dfs(1);
    print;
    end.

  • 0
    @ 2014-04-19 13:02:39

    明显树形动规。同意843279365,。,

  • 0
    @ 2013-12-03 17:57:35

    设f[i] 第i个人上台后的最大搞笑值
    设g[i] 第i个人不上台的最大搞笑值
    因此有f[i]=MAX(f[i],g[j]) (j是i的儿子)
    g[i]=MAX(g[i],f[j],g[j]) (j是i的儿子)

  • 0
    @ 2013-08-15 15:41:50

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 692 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 696 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 688 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 692 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 748 KiB, score = 10
    测试数据 #5: Accepted, time = 31 ms, mem = 760 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 704 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 740 KiB, score = 10
    测试数据 #8: Accepted, time = 31 ms, mem = 776 KiB, score = 10
    测试数据 #9: Accepted, time = 31 ms, mem = 776 KiB, score = 10
    Accepted, time = 154 ms, mem = 776 KiB, score = 100
    代码
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;

    vector<int>t[5005];
    int a[5005],d[5005][3];

    int dp(int i,int j) //j=1表示i参加,j=2表示i不参加
    {
    if(d[i][j]) return d[i][j];
    if(j==1){
    d[i][j]=a[i];
    for(vector<int>::iterator it=t[i].begin();it!=t[i].end();++it)
    d[i][j]+=dp(*it,2);
    }
    if(j==2){
    for(vector<int>::iterator it=t[i].begin();it!=t[i].end();++it)
    d[i][j]+=max(dp(*it,1),dp(*it,2));
    }
    return d[i][j];
    }

    int main()
    {
    ios::sync_with_stdio(false);
    int n,dad;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++)

    {
    cin>>dad;
    t[dad].push_back(i);
    }
    cout<<max(dp(1,1),dp(1,2))<<endl;
    return 0;
    }

  • 0
    @ 2013-04-29 14:06:42

    简单的树形动规
    VijosEx via JudgeDaemon2/13.4.6.0 via libjudge
    编译成功

    测试数据 #0: Accepted, time = 5 ms, mem = 98392 KiB, score = 10
    测试数据 #1: Accepted, time = 1 ms, mem = 98392 KiB, score = 10
    测试数据 #2: Accepted, time = 2 ms, mem = 98384 KiB, score = 10
    测试数据 #3: Accepted, time = 1 ms, mem = 98388 KiB, score = 10
    测试数据 #4: Accepted, time = 2 ms, mem = 98384 KiB, score = 10
    测试数据 #5: Accepted, time = 7 ms, mem = 98392 KiB, score = 10
    测试数据 #6: Accepted, time = 2 ms, mem = 98384 KiB, score = 10
    测试数据 #7: Accepted, time = 7 ms, mem = 98384 KiB, score = 10
    测试数据 #8: Accepted, time = 4 ms, mem = 98384 KiB, score = 10
    测试数据 #9: Accepted, time = 7 ms, mem = 98388 KiB, score = 10
    Accepted, time = 46 ms, mem = 98392 KiB, score = 100

  • 0
    @ 2012-07-19 17:09:56

    树形动规 但是用链表存图比较好,我用的是 邻接表 1..maxn 1..2000 过了

  • 0
    @ 2012-07-16 10:31:30

    明显树形动规

信息

ID
1706
难度
6
分类
动态规划 | 树形DP 点击显示
标签
(无)
递交数
1378
已通过
382
通过率
28%
被复制
1
上传者