树形dp的深入讨论

时间：2023-03-09 22:49:55
树形dp的深入讨论

　　越发向dp深入越发现dp越有意思！

　　树形dp的深入讨论

树形dp的深入讨论

这道题做的时候感觉十分的难，然后看完学长的题解恍然大悟。设状态不好导致想了一中午，一直感觉不可做，其实是自己的状态设的不对，这道题呢，首先是一个求在树上建多个厂，而也有一道类似的邮箱设置问题，这个则是在坐标轴上设邮局，但那个是四边形不等式优化的区间dp，这个则是一道树形dp了。

先设状态吧，f[i][0/1]表示第i个点建厂不建厂，发现有点问题你不知道距离i点最近的是哪个地方，于是多加一维表示距离最近的一个厂，这时发现还可以设几个厂没有体现出来那0/1发现可以省掉，直接替换，最后f[i][j][k]表示距离i点最近的有厂的j点，此时i点还可设k个厂，这就很显然了~\(^o^)/~

#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<iomanip>

#include<cmath>

#include<ctime>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<algorithm>

#define mod 1000007

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

int n,k,u=;

int v[maxn],dis[maxn];

int f[][][];//f[i][j][k]表示对于第i个点距离它最近的厂为点j，其中选择建立了k个厂

int rx[maxn],ls[maxn];//左儿子，右兄弟

int dfs(int x,int root,int k,int d)//x当前节点root距离x最近节点k表示还能再建几个厂d表示积累的距离

{

    if(x==-)return ;

    if(f[x][root][k]!=u)return f[x][root][k];

    for(int i=;i<=k;i++)//如果当前节点不建厂

    {

        int r=dfs(rx[x],root,i,d);

        int l=dfs(ls[x],root,k-i,d+dis[x]);

        int ans=(d+dis[x])*v[x];

        f[x][root][k]=min(f[x][root][k],l+r+ans);

    }

    for(int i=;i<k;i++)//当前选择建厂

    {

        int r=dfs(rx[x],root,i,d);

        int l=dfs(ls[x],x,k-i-,);

        f[x][root][k]=min(f[x][root][k],l+r);

    }

    return f[x][root][k];

}

int main()

{

    //freopen("1.in","r",stdin);

    memset(rx,-,sizeof(rx));

    memset(ls,-,sizeof(ls));

    n=read();k=read();

    for(int i=;i<=n;i++)

    {

        int x;

        v[i]=read();//当前节点生产出来的木块

        x=read();//i节点的父亲

        dis[i]=read();//i到x的距离

        rx[i]=ls[x];ls[x]=i;

    }

    memset(f,,sizeof(f));

    u=f[][][];

    printf("%d\n",dfs(,,k,));

    return ;

}

每个人都在追求成功，我呢，快乐就好啊。   ——等一个人咖啡

相关文章