31 条题解

  • 1
    @ 2017-04-05 22:15:00
  • 0
    @ 2018-02-24 21:23:14

    105是10^5
    May The Father Of Understanding Guide U

  • 0
    @ 2016-06-09 13:40:48

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>

    int N,M,K;

    struct Edge
    {
    int to,next;
    int weight;
    void assign(int t,int n,int w)
    {
    to=t; next=n; weight=w;
    }
    };

    Edge elist[605];
    int head[305];
    bool vis[305];
    int child[305][2]; //0 is left and 1 is right
    int weight[305];
    int ecnt;

    void initE()
    {
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(child,-1,sizeof(child));
    weight[1]=0;
    ecnt=0;
    }

    inline void addEdge(int from,int to,int weight)
    {
    elist[ecnt].assign(to,head[from],weight);
    head[from]=ecnt++;
    elist[ecnt].assign(from,head[to],weight);
    head[to]=ecnt++;
    }

    bool input()
    {
    scanf("%d%d%d",&N,&M,&K);
    bool ok=true;
    if(K+M-1>N) ok=false;
    initE();
    int a,b,c;
    for(int i=1;i<N;i++)
    {
    scanf("%d%d%d",&a,&b,&c);
    addEdge(a,b,c);
    }
    return ok;
    }

    void buildBinaryTree(int cur)
    {
    vis[cur]=true;
    int last=-1;
    for(int e=head[cur];e!=-1;e=elist[e].next)
    {
    int& to=elist[e].to;
    int& w=elist[e].weight;
    if(!vis[to])
    {
    weight[to]=w;
    if(last==-1)
    child[cur][0]=to;
    else
    child[last][1]=to;
    last=to;
    buildBinaryTree(to);
    }
    }
    }

    int dp[305][305][2];

    std::queue<int> seq;

    void getSeq(int cur)
    {
    if(child[cur][1]!=-1) getSeq(child[cur][1]);
    if(child[cur][0]!=-1) getSeq(child[cur][0]);
    seq.push(cur);
    }

    int solve_aux_3()
    {
    int ans;
    while(!seq.empty())
    {
    int cur=seq.front();
    seq.pop();
    int st(0);
    if(child[cur][1]!=-1) st|=1;
    if(child[cur][0]!=-1) st|=2;
    if(st==0)
    {
    dp[cur][0][0]=dp[cur][0][1]=0;
    dp[cur][1][0]=0;
    dp[cur][1][1]=weight[cur];
    }
    else if(st==1)
    {
    int& rc=child[cur][1];
    dp[cur][0][0]=0;
    for(int i=1;i<K;i++)
    dp[cur][i][0]=std::min(dp[rc][i][0],dp[rc][i-1][0]);
    dp[cur][0][1]=0;
    for(int i=1;i<K;i++)
    dp[cur][i][1]=std::min(dp[rc][i][1],dp[rc][i-1][1]+weight[cur]);
    }
    else if(st==2)
    {
    int& lc=child[cur][0];
    if(cur==1) ans=dp[lc][K-1][1];
    else
    {
    dp[cur][0][0]=dp[cur][0][1]=0;
    for(int i=1;i<K;i++)
    dp[cur][i][0]=std::min(dp[lc][i][0],dp[lc][i-1][1]);
    for(int i=1;i<K;i++)
    dp[cur][i][1]=std::min(dp[lc][i][0],dp[lc][i-1][1]+weight[cur]);
    }
    }
    else //st=3
    {
    int& lc=child[cur][0];
    int& rc=child[cur][1];
    dp[cur][0][0]=dp[cur][0][1]=0;
    for(int i=1;i<K;i++)
    {
    for(int j=0;j<=i;j++)
    dp[cur][i][0]=std::min(dp[lc][j][0]+dp[rc][i-j][0],dp[cur][i][0]);
    for(int j=0;j<i;j++)
    dp[cur][i][0]=std::min(dp[lc][j][1]+dp[rc][i-j-1][0],dp[cur][i][0]);
    }
    for(int i=1;i<K;i++)
    {
    for(int j=0;j<=i;j++)
    dp[cur][i][1]=std::min(dp[cur][i][1],dp[lc][j][0]+dp[rc][i-j][1]);
    for(int j=0;j<i;j++)
    dp[cur][i][1]=std::min(dp[cur][i][1],dp[lc][j][1]+dp[rc][i-j-1][1]+weight[cur]);
    }
    }
    }
    return ans;
    }

    int solve_aux_2()
    {
    int ans;
    while(!seq.empty())
    {
    int cur=seq.front();
    seq.pop();
    int st(0);
    if(child[cur][1]!=-1) st|=1;
    if(child[cur][0]!=-1) st|=2;
    if(st==0)
    {
    dp[cur][0][1]=dp[cur][1][0]=0;
    dp[cur][0][0]=dp[cur][1][1]=weight[cur];
    }
    else if(st==1)
    {
    int& rc=child[cur][1];
    dp[cur][0][1]=dp[rc][0][1];
    dp[cur][0][0]=dp[rc][0][0]+weight[cur];
    for(int i=1;i<K;i++)
    {
    dp[cur][i][0]=std::min(dp[rc][i][0]+weight[cur],dp[rc][i-1][0]);
    dp[cur][i][1]=std::min(dp[rc][i][1],dp[rc][i-1][1]+weight[cur]);
    }
    }
    else if(st==2)
    {
    int& lc=child[cur][0];
    if(cur==1) ans=dp[lc][K-1][1];
    else
    {
    dp[cur][0][1]=dp[lc][0][0];
    dp[cur][0][0]=dp[lc][0][0]+weight[cur];
    for(int i=1;i<K;i++)
    {
    dp[cur][i][0]=std::min(dp[lc][i][0]+weight[cur],dp[lc][i-1][1]);
    dp[cur][i][1]=std::min(dp[lc][i][0],dp[lc][i-1][1]+weight[cur]);
    }
    }
    }
    else
    {
    int& lc=child[cur][0];
    int& rc=child[cur][1];
    dp[cur][0][1]=dp[lc][0][0]+dp[rc][0][1];
    dp[cur][0][0]=dp[lc][0][0]+dp[rc][0][0]+weight[cur];
    for(int i=1;i<K;i++)
    {
    for(int j=0;j<=i;j++)
    dp[cur][i][0]=std::min(dp[cur][i][0],dp[lc][j][0]+dp[rc][i-j][0]+weight[cur]);
    for(int j=0;j<i;j++)
    dp[cur][i][0]=std::min(dp[cur][i][0],dp[lc][j][1]+dp[rc][i-j-1][0]);
    for(int j=0;j<=i;j++)
    dp[cur][i][1]=std::min(dp[cur][i][1],dp[lc][j][0]+dp[rc][i-j][1]);
    for(int j=0;j<i;j++)
    dp[cur][i][1]=std::min(dp[cur][i][1],dp[lc][j][1]+dp[rc][i-j-1][1]+weight[cur]);
    }
    }
    }
    return ans;
    }

    int solve()
    {
    memset(dp,0x3f,sizeof(dp));
    buildBinaryTree(1);
    getSeq(1);
    return M==2?solve_aux_2():solve_aux_3();
    }

    int main()
    {
    if(!input()) printf("-1");
    else printf("%d",solve());
    return 0;
    }
    为啥你萌都说这题很水(´・ω・`)

  • 0
    @ 2016-01-03 20:19:18

    又A了一道水题,谁能告诉我vijos上的Win版MC怎么打开啊啊啊!!!
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int point[303],next[603],v[603],c[603],cnt=0,N,M,K,f[303][303][2],d[303],con[303],pre[303];
    int l[303],r[303];
    bool p[303];
    void insect(int x,int y,int z){next[cnt]=point[x];point[x]=cnt;v[cnt]=y;c[cnt]=z;cnt++;}
    void dfs(int x)
    {
    int i,j=-1;
    for (i=point[x];i!=-1;i=next[i])
    if (p[v[i]]==0)
    {
    p[v[i]]=1;
    if (l[x]==0) l[x]=v[i],d[v[i]]=c[i],pre[v[i]]=0,j=l[x]; else
    {
    r[j]=v[i]; d[v[i]]=c[i]; pre[r[j]]=j; j=r[j];
    }
    }
    if (j==-1) return;
    dfs(j); con[j]=con[l[j]]+1;
    while (pre[j]!=0) j=pre[j],dfs(j),con[j]=con[l[j]]+con[r[j]]+1;
    }
    int dp(int x,int k,int t)
    {
    if (x==0) return 0;
    if (f[x][k][t]!=-1) return f[x][k][t];
    int i,l1,r1,num=1000000000;
    for (i=0;i<k;++i)
    if ((i<=con[l[x]])&&(k-1-i<=con[r[x]]))
    {
    l1=dp(l[x],i,1);
    r1=dp(r[x],k-1-i,t);
    num=min(num,l1+r1+(t==1)*d[x]);
    }
    for (i=0;i<=k;++i)
    if ((i<=con[l[x]])&&(k-i<=con[r[x]]))
    {
    l1=dp(l[x],i,0);
    r1=dp(r[x],k-i,t);
    num=min(num,l1+r1+(M==2)*(t==0)*d[x]);
    }f[x][k][t]=num;
    return num;
    }
    int main()
    {
    memset(point,-1,sizeof(point));
    memset(next,-1,sizeof(next));
    memset(f,-1,sizeof(f));
    memset(v,0,sizeof(v));
    memset(c,0,sizeof(c));
    memset(p,0,sizeof(p));
    scanf("%d %d %d\n",&N,&M,&K);
    if (K+M-1>N) {printf("-1\n");return 0;}
    int i,a,b,c;
    for (i=1;i<N;++i)
    {
    scanf("%d %d %d\n",&a,&b,&c);
    insect(a,b,c);insect(b,a,c);
    }p[1]=1; dfs(1);
    printf("%d\n",dp(l[1],K-1,1));
    return 0;
    }

  • 0
    @ 2014-09-09 21:24:22

    树状DP 寻找根节点
    #include<cstdio>

    #include<iostream>

    #include <algorithm>

    #include <cstdlib>

    #include<cstring>
    using namespace std;
    #define maxv 301
    #define maxint 200000000
    typedef struct NODE
    {
    long x,l,r;
    }node;
    long m,n,k,root,father[maxv]={0},w[maxv][maxv]={0};
    long f[maxv][maxv][2],num[maxv]={0},ans;
    node tree[maxv];
    void ins(long fa,long son)
    {
    long p;
    if(tree[fa].l==0)
    tree[fa].l=son;
    else
    {
    p=tree[fa].l;
    while(tree[p].r!=0)
    p=tree[p].r;
    tree[p].r=son;
    }
    }
    void count(long node)
    {
    long x1,x2;
    if(node==0) return;
    num[node]=1;
    x1=tree[node].l;
    count(x1);
    num[node]+=num[x1];
    x2=tree[node].r;
    count(x2);
    num[node]+=num[x2];
    }
    void init()
    {
    long i,j,fa,son,weight;
    scanf("%ld%ld%ld",&n,&m,&k);// N个顶点 M个头 吃掉K个
    for(i=1;i<=n;i++)
    {
    tree[i].x=i;
    tree[i].l=tree[i].r=0;
    }
    for(i=1;i<=n-1;i++)
    {
    scanf("%ld%ld%ld",&fa,&son,&weight);
    ins(fa,son);
    father[son]=fa;
    w[fa][son]=weight;
    }
    for(i=1;i<=n;i++)
    if(father[i]==0)
    {
    root=i;
    break;
    }
    for(i=0;i<=n;i++)
    for(j=0;j<=n;j++)
    {
    f[i][j][0]=-1;
    f[i][j][1]=-1;
    }
    count(root);
    }
    long d(long i,long j)
    {
    if((i==0&&j==0&&m==2)||(i==1&&j==1))
    return 1;
    return 0;
    }
    long dp(long node,long nn,long kk)
    {
    if(f[node][nn][kk]!=-1)
    return f[node][nn][kk];
    if(node==0) return 0;
    long i,x1,x2,t;
    f[node][nn][kk]=maxint;
    x1=tree[node].l;
    x2=tree[node].r;
    for(i=0;i<=num[x1];i++)
    {
    if(i>=nn-num[x2]-1&&i<=nn-1)
    {
    t=dp(x1,i,1)+dp(x2,nn-i-1,kk)+d(1,kk)*w[father[node]][node];
    if(t<f[node][nn][kk]) f[node][nn][kk]=t;
    }
    if(i>=nn-num[x2]&&i<=nn&&node!=root)// 只有此结点不是根节点才有可能不被大头吃掉
    {
    t=dp(x1,i,0)+dp(x2,nn-i,kk)+d(0,kk)*w[father[node]][node];
    if(t<f[node][nn][kk]) f[node][nn][kk]=t;
    }
    }
    return f[node][nn][kk];
    }
    void write()
    {
    printf("%ld\n",ans);
    }
    int main()
    {
    init();
    if(n>=k+m-1)
    ans=dp(root,k,0);
    else ans=-1;
    write();
    return 0;
    }

  • 0
    @ 2009-08-07 16:51:12

    [blue]

    编译通过...

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

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

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

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

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

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

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

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

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

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

    多叉树转二叉树

    [red]

    树型dp

    f表示i为跟的子树

    d=1 表示大头吃掉fa[i]

    d=0 表示小头吃掉fa[i]

    大头吃掉以i为跟的子树

    k个果子的最小代价,

    方程就很简单了

    f:=min(f[left[i],1,j]+f[right[i],d,k-j-1]+dist[fa[i],i]*b[d,1] ( 0

  • 0
    @ 2009-07-14 20:58:17

    被我用多叉树硬A掉了!

  • 0
    @ 2009-04-29 20:09:47

    黑书p142-143,讲的很清楚了,自己看看吧。

    提醒一下,一开始写了一个记忆化搜索,后面的基本全超时,建议不要写。

  • 0
    @ 2009-04-04 10:57:23

    注意几点

    1.过程调用不是一般的慢,最好还是用函数调用

    2.不要默认边>0

    3.转二叉程序更简洁,思路更明确

    4.有个小小的儿子树优化

    就是当分给大头的果子数NEED>SON[now]时,无需计算,直接返回oo

  • 0
    @ 2009-03-31 19:54:40

    我知道方程,怎么会超时的呢

    function f(i,j,k:longint):longint;

    var j1,x1,x2:longint;

    begin

    if j>sum[i] then exit(oo);

    if dp>0 then exit(dp);

    if (i=0)and(j=0) then exit(0);

    x1:=tree[i].l;x2:=tree[i].r;

    dp:=oo;

    for j1:=0 to min(j-1,sum[x1]) do

    dp:=min(f(x1,j1,0)+f(x2,j-j1-1,k)+d(k,0)*cost,dp);

    for j1:=0 to min(j,sum[x1]) do

    dp:=min(f(x1,j1,1)+f(x2,j-j1,k)+d(k,1)*cost,dp);

    f:=dp;

    end;

    大牛罩我

  • -1
    @ 2015-05-14 19:47:14

    又是1A好难过

  • -1
    @ 2010-03-18 18:45:47

    树形动规,说是转二叉但是感觉没什么区别。。。

  • -1
    @ 2009-11-10 20:23:51

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

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

    九头龙吃了我的期中考试...

  • -1
    @ 2009-10-23 08:38:03

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

    诧异了...d[0,0]和d[1,1]打反了.....

    参考了《算法艺术与信息学竞赛》的题解,可是惊奇的发现书上居然写错了.......

  • -1
    @ 2009-10-10 20:11:59

    终于AC了

    本人第一道多叉转2叉

    高兴ING

  • -1
    @ 2009-09-19 13:14:36

    编了30分钟100行,本以为可以了,但是...

    查错查了一个晚上

    8个点到10个点就那么难吗~~

    人世间最难过的莫过于此~~~

  • -1
    @ 2009-09-18 13:50:25

    多叉树型也好理解!!!!!!

  • -1
    @ 2009-09-08 20:23:32

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    细节问题 太痛苦了

    总算AC了 。。。囧了好久

  • -1
    @ 2009-09-06 13:53:38

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    记忆化搜索....

    答案输出应该是 f(lchild[1],k-1,1) 调试了一个晚上都没发现

    方程见 算法艺术

  • -1
    @ 2009-07-03 21:01:53

    Orz大牛们!

信息

ID
1523
难度
5
分类
动态规划 | 树形DP 点击显示
标签
递交数
748
已通过
237
通过率
32%
被复制
3
上传者