/ Vijos / 题库 / 河流 /

题解

27 条题解

  • 1
    @ 2016-10-25 16:11:20

    来一发

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #define INF 0x7f7f7f7f
    using namespace std;
    struct node{
    int left,right,num,dis;
    }gg[105];
    int dui[105],deep[105],child[105],f[105][105][51],tot,fa[105];
    void dfs(int k,int dep)
    {
    dui[++tot]=k;
    deep[k]=dep+gg[k].dis;
    int i=gg[k].left;
    while(i)
    {
    dfs(i,deep[k]);
    i=gg[i].right;
    }
    }
    int main()
    {
    int n,K;
    cin>>n>>K;
    memset(fa,-1,sizeof fa);
    for(int i=1;i<=n;i++)
    {
    int a,b,c;
    cin>>a>>b>>c;
    if(!child[b])
    gg[b].left=i;
    else
    gg[child[b]].right=i;
    child[b]=i;
    gg[i].num=a;
    gg[i].dis=c;
    fa[i]=b;
    }
    dfs(0,0);
    int llll;
    memset(f,INF,sizeof f);
    memset(f[0],0,sizeof f[0]);
    for(int i=n+1;i>=2;i--)
    {
    int now=dui[i];
    int le=gg[now].left;
    int ri=gg[now].right;
    for(int j=fa[now];j!=-1;j=fa[j])
    for(int k=0;k<=K;k++)
    {
    for(int l=0;l<=k;l++)
    if(f[le][j][l]!=INF&&f[ri][j][k-l]!=INF)
    {
    int add=gg[now].num*(deep[now]-deep[j]);
    int op=f[le][j][l]+f[ri][j][k-l]+add;
    f[now][j][k]=min(f[now][j][k],op);
    }
    for(int l=0;l<k;l++)
    if(f[le][now][l]!=INF&&f[ri][j][k-l-1]!=INF)
    {
    int op=f[le][now][l]+f[ri][j][k-l-1];
    f[now][j][k]=min(op,f[now][j][k]);
    }
    }
    }
    printf("%d",f[gg[0].left][0][K]);
    }

  • 0
    @ 2016-01-02 20:28:46

    我的AC率啊,为何每第一次交都*CE*?
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    bool p[103];
    int N,K,point[103],next[203],v[203],c[203],w[103],cnt=0;
    int f[103][103][103],l[103],r[103],dist[103];
    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;
    for (i=point[x];i!=-1;i=next[i])
    if (p[v[i]]==0)
    {
    if (l[x]==0) l[x]=v[i],dist[v[i]]=dist[x]+c[i]; else
    {
    j=l[x];
    while (r[j]!=0) j=r[j];
    r[j]=v[i]; dist[v[i]]=dist[x]+c[i];
    }p[v[i]]=1;
    }
    i=l[x]; while (i!=0){dfs(i);i=r[i];}
    }
    int dp(int x,int fa,int k)
    {
    if (x==0) return 0;
    if (f[x][fa][k]!=-1) return f[x][fa][k];
    if (k==0) {
    int now=(dist[x]-dist[fa])*w[x];
    if (l[x]!=0) now+=dp(l[x],fa,k);
    if (r[x]!=0) now+=dp(r[x],fa,k);
    f[x][fa][k]=now; return now;
    }
    int i;f[x][fa][k]=2000000001;
    for (i=0;i<=k;++i)
    f[x][fa][k]=min(f[x][fa][k],dp(l[x],fa,i)+dp(r[x],fa,k-i)+w[x]*(dist[x]-dist[fa]));
    for (i=0;i<k;++i)
    f[x][fa][k]=min(f[x][fa][k],dp(l[x],x,i)+dp(r[x],fa,k-1-i));
    return f[x][fa][k];
    }
    int main()
    {
    memset(point,-1,sizeof(point));
    memset(next,-1,sizeof(next));
    memset(dist,0,sizeof(dist));
    memset(v,-1,sizeof(v));
    memset(f,-1,sizeof(f));
    memset(c,0,sizeof(c));
    memset(w,0,sizeof(w));
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    memset(p,0,sizeof(p));
    scanf("%d %d\n",&N,&K);
    int i,di,vi;
    for (i=1;i<=N;++i)
    {
    scanf("%d %d %d\n",&w[i],&vi,&di);
    insect(i,vi,di);insect(vi,i,di);
    }p[0]=1;dfs(0);
    printf("%d\n",dp(l[0],0,K));
    return 0;
    }

  • 0
    @ 2015-05-02 11:33:18

    树形DP 记忆化搜索

    #include<cmath>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define sz 110
    #define LL long long
    #define for1(v,a,b) for (int v=a;v<=b;v++)
    #define for2(v,a,b) for (int v=a;v>=b;v--)
    using namespace std;
    int left[sz],right[sz];
    int w[sz],d[sz],f[sz][sz][sz];
    int n,k,p;
    int DP(int from,int to,int k,int s){
    if ((from==n+1)||(to==n+1)) return 0;
    if (f[from][to][k]!=-1) return f[from][to][k];
    int x=2000000010;
    for1(i,0,k-1) //都怪你
    x=min(x,DP(left[from],from,i,0)+DP(right[from],to,k-i-1,s));
    for1(i,0,k)
    x=min(x,DP(left[from],to,i,s+d[from])+DP(right[from],to,k-i,s)+(s+d[from])*w[from]);
    f[from][to][k]=x;
    return x;
    }
    int main(){
    //freopen("p1.in","r",stdin);
    scanf("%d%d",&n,&k);
    for1(i,0,n){
    left[i]=n+1;
    right[i]=n+1;
    for1(j,0,n)
    for1(p,0,k)
    f[i][j][p]=-1;
    }
    for1(i,1,n){
    scanf("%d%d%d",&w[i],&p,&d[i]);
    right[i]=left[p];
    left[p]=i;
    }
    printf("%d",DP(left[0],0,k,0));
    return 0;
    }

  • 0
    @ 2013-11-04 23:14:58

    这个输入文件不对吧,我的AC率啊!

  • 0
    @ 2013-07-26 11:17:45

    又 A 一遍 膜拜 嘉林God Orz +1
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<iostream>
    #define INF 99999999
    long long l[111],r[111],dis[111][111],w[111],f[111][111][111];
    int n,m;
    int max(int ax,int by){
    return ax>by ? ax : by;
    }
    int min(int ax,int by){
    return ax>by ? by : ax;
    }
    void insert(int k,int F){
    if(!l[F]){l[F]=k;return;}
    F=l[F];
    while(r[F]) F=r[F];
    r[F] = k;
    }
    int Dp(int now,int F,int k){
    if(!now) return 0;
    if(f[now][F][k]!=-1) return f[now][F][k];
    int M=w[now]*dis[now][F];
    if(!k) return f[now][F][k]=Dp(l[now],F,0)+Dp(r[now],F,0)+ M ;
    if(!l[now]&&!r[now]) return 0;
    f[now][F][k]=INF;
    for(int i=0;i<=k;i++) f[now][F][k]=min(f[now][F][k],M+Dp(l[now],F,k-i)+Dp(r[now],F,i));
    for(int i=0;i<k ;i++) f[now][F][k]=min(f[now][F][k],Dp(l[now],now,k-i-1)+Dp(r[now],F,i));
    return f[now][F][k];
    }
    int main(){
    // freopen("xx.in","r",stdin);
    //freopen("xx.out","w",stdout);
    scanf("%d%d",&n,&m);
    memset(dis,1,sizeof(dis));
    for(int i=1;i<=n;i++) dis[i][i]=0;
    for(int i=1;i<=n;i++){
    int u,L;
    scanf("%d%d%d",&w[i],&u,&L);
    dis[u][i]=dis[i][u]=L;
    insert(i,u);
    }
    for(int k=0;k<=n;k++)
    for(int j=0;j<=n;j++)
    for(int i=0;i<=n;i++)
    if(dis[i][j]>dis[i][k]+dis[k][j])
    dis[i][j]=dis[i][k]+dis[k][j];
    /* for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) printf("%d ",dis[i][j]);
    printf("\n");
    }*/
    memset(f,-1,sizeof(f));
    printf("%d",Dp(l[0],0,m));
    }

  • 0
    @ 2013-04-11 10:38:52

    AC +1 以下代码 题解见LS。。
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<string>
    long long left[111],right[111],d[111][111],w[111],a, f[111][111][111];
    int n,m,v,di,wi;

    void find (int k,int root)
    {
    if(right[root]==0){
    right[root]=k;
    return ;
    }
    root=right[root];
    while(left[root]!=0) root=left[root];
    left[root]=k;
    }
    int min(int a,int b,int c)
    {
    int ans=a;
    if(b<ans) ans=b;
    if(c<ans) ans=c;
    return ans;
    }

    void work()
    {
    for(int i=0;i<=n;i++) d[i][i]=0;
    for(int k=0;k<=n;k++)
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
    if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];

    }
    int Dp(int now,int num,int root)
    {
    if(now==0) return 0;

    if(f[now][num][root]>=0) return f[now][num][root];
    int money=w[now]*d[now][root];
    if(num==0)
    {
    f[now][num][root]=Dp(left[now],0,root)+Dp(right[now],0,root)+money;
    return f[now][num][root];
    }

    if(left[now]==0&&right[now]==0)
    {
    f[now][num][root]=0;
    return 0;

    }
    f[now][num][root]=Dp(right[now],num,root)+Dp(left[now],0,root)+money;
    for(int k=0;k<num;k++)
    f[now][num][root]=min(Dp(right[now],k,root)+Dp(left[now],num-k,root)+money,Dp(right[now],k,now)+Dp(left[now],num-k-1,root),f[now][num][root]);
    return f[now][num][root];
    }
    int main()
    {
    //freopen("xx.in","r",stdin);
    // freopen("xx.out","w",stdout);
    scanf("%d%d",&n,&m);
    memset(d,1,sizeof(d));
    for(int i=1;i<=n;i++)
    {
    scanf("%d%d%d",&w[i],&v,&a);
    d[i][v]=d[v][i]=a;
    find(i,v);

    }
    work();

    memset(f,-1,sizeof(f));
    printf("%d",Dp(right[0],m,0));
    }

  • 0
    @ 2010-04-08 20:22:56

    O(N^3) 的状态 , O(N) 的 转移, 居然 也能 秒杀。。。

  • 0
    @ 2010-03-14 14:54:17

    请问这题怎么优化可以秒杀第21个测试点?

  • 0
    @ 2009-11-10 15:36:29

    多叉转两叉,得益于贪吃的九头蛇,好题,一年前我还没做出啊

  • 0
    @ 2009-11-09 22:33:03

    [让人囧的记录,95分也算AC了囧囧]

    自己的方法:多叉树转二叉树再进行记忆化搜索。写起来十分方便

    多叉转二叉的作用:对于每个根root,根的左孩子left[root]是根的真正孩子,而根的右孩子right[root]是根的兄弟

    详见M67的博文。

    这样一来转移方程就很好写了

    f表示以i为根的子树分配j个伐木场离i最近的一个下流的伐木场在k。

    f:=

    MAX{f[left[i],0..j,k]+f[right[i],j..0,k]}:是i这个点不放伐木场

    MAX{f[left[i],0..j-1,i]+f[right[i],j-1..0,k]}:是i这个点设置伐木场

    Orz此题 是个好题 值得一做

  • 0
    @ 2009-11-03 00:20:34

    ..exit写错位置了.. 超时N次........

  • 0
    @ 2009-09-24 18:29:12

    还是多叉DP快啊!!sunny都秒杀^.^

    只是细节太多

  • 0
    @ 2009-08-07 11:18:15

    本沙茶的程序最后一个点巨慢……

  • 0
    @ 2009-07-22 16:12:15

    int64居然挂了,longword居然ac

    树型三维dp

  • 0
    @ 2009-04-29 13:18:23

    算法:三维DP

    数据结构:左孩子右兄弟

    实现:记忆化搜索

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-04-16 16:54:25

    难度三是因为n太小了

    要是n在10000以上就有难度了

  • 0
    @ 2009-04-06 17:44:44

    时间复杂度ms是n*k*k

    背包咱想到了

    三维也想到了

    垃圾若死也打开了

    一个声音高叫着

    爬出来吧,给你标程

    但我深知道

    人的身躯,怎能从那数据线中爬出

    唉,减肥去也

  • 0
    @ 2009-03-28 20:12:14

    我们需要先把所有点对点的路径预处理好。

    分两种情况,m枚举在儿子处造几个场

    I位置不造场

    F=min{f[son[i],m,k]+f[next[i],j-m,k]}+w

    I位置造场,这时son[i]连到i

    F=min{f[son[i],m,i]+f[next[i],j-m-1,k]}

    把0当作跟会使编程方便。

  • 0
    @ 2009-03-15 19:37:23

    3维,否则绝对后效.

  • 0
    @ 2009-03-15 19:34:10

    我写的三维动态规划,如果不是像李永刚那么强的话,最好不要写O(n^2) 的算法,

    李永刚大牛曾经给我讲过,可是没有听懂。

信息

ID
1518
难度
4
分类
动态规划 | 树形DP 点击显示
标签
递交数
509
已通过
201
通过率
39%
被复制
3
上传者