题解

42 条题解

  • 1
    @ 2017-05-28 13:35:07
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    struct p_s_1
    {
        int v;
        vector<int> s;
    };
    
    int n,m;
    vector<vector<int> > f;
    vector<p_s_1> a;
    
    void work_1(int now)
    {
        vector<int> v;
        v.resize(m+1,0);
        for (int i=1;i<a[now].s.size();i++)
        {
            work_1(a[now].s[i]);
            for (int j=m;j>0;j--)
                for (int k=j;k>0;k--)
                    v[j]=max(v[j],v[j-k]+f[a[now].s[i]][k]);
        }
        for (int i=m;i>0;i--)
            f[now][i]=max(f[now][i],v[i-1]+a[now].v);
    }
    
    int main()
    {
        while (~scanf("%d%d",&n,&m))
        {
            a.resize(n+1);
            for (int i=1;i<=n;i++)
            {
                int s_n;
                scanf("%d%d",&a[i].v,&s_n);
                a[i].s.resize(s_n+1,0);
                for (int j=1;j<=s_n;j++)
                    scanf("%d",&a[i].s[j]);
            }
            f.resize(n+1);
            for (int i=1;i<=n;i++)
                f[i].resize(m+1,0);
            work_1(1);
            printf("%d\n",f[1][m]);
        }
    }
    
  • 0
    @ 2016-11-10 23:48:44

    vijos的评测机就是快...暴力都能过
    第一个点输出0不是负数

  • 0
    @ 2016-08-20 10:44:52

    多叉转成二叉,哪里错了?
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #define N 1010
    #define INF 1000000001
    using namespace std;
    int n,m;
    int v[N];
    struct data
    {
    int l,r;
    }a[N];
    void add(int w,int c)
    {
    int p=a[w].l;
    if(a[w].l==0)a[w].l=c;
    else
    {
    while(a[p].r!=0)
    p=a[p].r;
    a[p].r=c;
    }
    }
    int f[1001][1001];
    void dfs(int w,int num)
    {
    int p;
    if(w==0||num==0)
    {
    f[w][num]=0;
    return;
    }
    if(f[w][num]!=-1)
    return;
    dfs(a[w].r,num);
    f[w][num]=f[a[w].r][num];
    for(int k=0;k<num;k++)
    {
    dfs(a[w].l,k);
    dfs(a[w].r,num-k-1);
    f[w][num]=max(f[w][num],f[a[w].l][k]+f[a[w].r][num-1-k]+v[w]);
    }
    }
    int main()
    {
    //freopen("D://in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    for(int j=1;j<=m;j++)
    f[i][j]=-1;
    }
    for(int i=1;i<=n;i++)
    {
    int s;
    scanf("%d%d",&v[i],&s);
    for(int j=1;j<=s;j++)
    {
    int t;
    scanf("%d",&t);
    add(i,t);
    }
    }
    dfs(1,m);
    cout<<f[1][m];
    return 0;
    }

  • 0
    @ 2014-08-18 17:54:21

    评测结果
    编译成功

    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
    63 lines compiled, 0.1 sec , 28400 bytes code, 1628 bytes data

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

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

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

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

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

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

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

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

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

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

    Accepted, time = 137 ms, mem = 8608 KiB, score = 100

    代码
    var
    n,m,t:longint;
    a,list,count:array[0..1000]of longint;
    f,table:array[0..1000,0..1000]of longint;
    procedure dfs(x:longint);
    var
    i:longint;
    begin
    t:=t+1;
    list[t]:=x;
    for i:=1 to table[x,0]do
    begin
    dfs(table[x,i]);
    count[x]:=count[x]+count[table[x,i]];
    end;
    count[x]:=count[x]+1;
    end;
    procedure int;
    var
    i,j,k,s:longint;
    begin
    fillchar(table,sizeof(table),0);

    read(n,m);
    for i:=1 to n do
    begin
    read(a[i],s);
    table[i,0]:=s;
    for j:=1 to s do
    begin
    read(k);
    table[i,j]:=k;
    end;
    end;
    t:=0;
    dfs(1);
    end;
    function max(x,y:longint):longint;
    begin
    if x>y then exit(x);
    exit(y);
    end;
    procedure doing(v,x:longint);
    var
    i,j:longint;
    begin
    for i:=1 to n do
    begin
    f[i,0]:=0;
    f[i,1]:=a[list[i]];
    end;
    for i:=n downto 1 do
    for j:=1 to m do
    f[i,j]:=max(f[i+1,j-1]+a[list[i]],f[i+count[list[i]],j]);

    end;
    begin
    int;
    doing(1,m);
    write(f[1,m]);
    end.

  • 0
    @ 2014-08-18 17:39:25

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

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

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

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

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

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

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

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

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

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

    Accepted, time = 82 ms, mem = 196444 KiB, score = 100

  • 0
    @ 2014-08-18 17:38:50

    var
    list,count,a:array[0..5000] of longint;

    table,opt:array[0..5000,0..5000] of longint;

    c,w,m,s,t,i,j,top,sum,n,k:longint;
    function max(a,b:longint):longint;
    begin
    if a>b then exit(a);
    exit(b);
    end;

    function dfs(k:longint):longint;
    var
    i:longint;
    begin
    top:=top+1;
    list[top]:=k;
    for i:=1 to table[k,0] do
    count[k]:=count[k]+dfs(table[k,i]);
    count[k]:=count[k]+1;
    exit(count[k]);
    end;

    procedure dp(v,x:longint);
    var i,j:longint;
    begin
    for i:=1 to n do
    begin
    opt[i,0]:=0;
    opt[i,1]:=a[list[i]];
    end;

    for i:=n downto 1 do
    for j:=1 to m do
    opt[i,j]:=max(opt[i+1,j-1]+a[list[i]],opt[i+count[list[i]],j])
    end;
    begin

    read(n,m);
    for i:=1 to n do
    begin
    read(a[i],s);
    table[i,0]:=s;

    for j:=1 to s do
    begin
    read(w);
    table[i,j]:=w;
    end;

    end;
    dp(1,m);
    writeln(opt[1,m]);
    end.
    请勿直接粘贴 我删除了几句 主要看算法

  • 0
    @ 2014-08-18 17:34:31

    var
    f:array[0..1001,0..1001]of longint;
    count,list,left,right,p:array[0..1001]of longint;
    sum,top,t,s,j,n,m,i:longint;
    function max(a,b:longint):longint;
    begin
    if a>b then
    exit(a)
    else
    exit(b);
    end;
    function dfs(k:integer):longint;
    var
    t:integer;
    begin
    t:=0;
    top:=top+1;
    list[top]:=k;
    count[k]:=1;
    if left[k]>0 then
    count[k]:=dfs(left[k])+1;
    if right[k]>0 then
    t:=dfs(right[k]);
    exit(count[k]+t);
    end;
    begin

    read(n,m);
    for i:=1 to n do
    begin
    read(p[i],s);
    for j:=1 to s do
    begin
    read(t);
    right[t]:=left[i];
    left[i]:=t;
    end;
    end;
    dfs(1);
    for i:=1 to n do
    begin
    f[i,0]:=0;
    f[i,1]:=p[list[i]];
    end;
    for i:=n-1 downto 0 do
    for j:=1 to m do
    f[i,j]:=max(f[i+1,j-1]+p[list[i]],f[i+count[list[i]],j]);
    for i:=1 to m do
    sum:=max(sum,f[1,i]);
    writeln(sum);
    end.

  • 0
    @ 2009-11-08 21:38:15

    第一个数据点竟然是负的!!!XD

    WA N次后writeln('0')解决!!

    o(nm)算法请看WC2005何森论文中的算法三

  • 0
    @ 2009-10-29 08:29:29

    orz orz orz orz

    orz orz orz orz

    noi2009徐持衡论文~~

  • 0
    @ 2009-10-27 19:08:27

    怨念啊。。

    记录下个子树的数组调用时下表写错了,浪费昨天一晚上时间,6次提交

    话说先序遍历的时候,在所有儿子调用完之后先序遍历的指针就刚好指向下一个子树的位置,直接记录就行了-.-

  • 0
    @ 2009-10-25 12:43:44

    边界是 f[n,i]:=max(0,p[a[n]])! 不是 f[n,i]:=max(0,p[n]);

    要不然就一直90了.当然对于这道题,n+1的边界可以不写,正好是0.

    程序还不到40行...很好写

  • 0
    @ 2009-10-22 21:28:02

    终于AC了,提示一下,m可以不选

  • 0
    @ 2009-10-14 22:01:57

    program v1642;

    var

    f,child:array[1..1001,0..1000]of longint;

    father,p,s,c,a:array[1..1000]of longint;

    i,j,k,n,m:longint;

    procedure work(r:longint);

    var

    i,j:longint;

    begin

    inc(k);

    a[k]:=r;

    for i:=1 to s[r] do

    work(child[r,i]);

    for i:=1 to s[r] do

    c[r]:=c[r]+c[child[r,i]];

    c[r]:=c[r]+s[r];

    end;

    begin

    k:=0;

    read(n,m);

    fillchar(a,sizeof(a),0);

    for i:=1 to n do

    begin

    read(p[i],s[i]);

    for j:=1 to s[i] do

    begin

    read(child);

    father[child]:=i;

    end;

    end;

    k:=0;

    work(1);

    for i:=n downto 1 do

    begin

    for k:=1 to m do

    begin

    if f+p[a[i]]>f[i+c[a[i]]+1,k] then

    f:=f+p[a[i]]

    else f:=f[i+c[a[i]]+1,k];

    end;

    end;

    writeln(f[1,m]);

    end.

    TMD奇怪

    WA了N次,后来把边界判断删了就A了

  • 0
    @ 2009-09-19 20:29:00

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    不在树形上的树形动规

    感谢 chenxiaomi 的网址! N*M 秒杀

  • 0
    @ 2009-09-19 18:00:09

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

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

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

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

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

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

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

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

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

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

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

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

    pay attention to 边界!!!!!!!!!!!!!!!

  • 0
    @ 2009-10-06 10:50:20

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

    国家队论文实在太伟大了!O(NM)的算法实在太伟大了!

    传统的树形DP只能超时....(注意班长一定要取!)

    也感谢各位大牛的指教~

  • 0
    @ 2009-09-12 14:55:28

    大牛们发个pascal码好吗?谢谢了。

  • 0
    @ 2009-09-06 20:48:27

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    #include

    using namespace std;

    const int maxn = 1010, maxm = 10010;

    const int oo = 1000000000;

    struct Tnode

    {

    int son, next;

    }tn[maxn];

    int n, m;

    int p[maxn];

    int val[maxn];

    int son_count[maxn];

    int cur = 0;

    int f[maxn][maxm];

    void insert(int root, int son)

    {

    cur++;

    tn[cur].son = son;

    tn[cur].next = p[root];

    p[root] = cur;

    }

    void get_sonCount(int root)

    {

    int next = p[root];

    while(next != 0)

    {

    get_sonCount(tn[next].son);

    son_count[root] += son_count[tn[next].son];

    next = tn[next].next;

    }

    son_count[root]++;

    }

    void dfs(int root)

    {

    f[root][0] = 0;

    f[root][1] = val[root];

    int next = p[root];

    int haved = 1;

    while(next != 0)

    {

    int son = tn[next].son;

    dfs(son);

    int tmp = min(haved,m);

    haved += son_count[son];

    for(int i = min(haved,m); i > 1; i--)

    {

    for(int j = min(i-1, son_count[son]); j >= 1; j--)

    {

    if(i-j>tmp) break;

    f[root][i] >?= f[root] + f[son][j];

    }

    }

    next = tn[next].next;

    }

    }

    int main()

    {

    cin>>n>>m;

    for(int i = 1; i >val[i];

    int tmp;

    cin>>tmp;

    while(tmp > 0)

    {

    tmp--;

    int son;

    cin>>son;

    insert(i, son);

    }

    }

    get_sonCount(1);

    for(int i = 1; i

  • 0
    @ 2009-10-26 09:59:38

    谁给一下O(NM)算法的论文

信息

ID
1642
难度
8
分类
动态规划 | 树形DP 点击显示
标签
递交数
1797
已通过
253
通过率
14%
被复制
1
上传者