树形DP get ！

A4paper · 2018-03-30 21:25:00 · 个人记录

入门：

传送门

一遍切绿怎么说，老哥稳。

定义 f[i][0/1] 表示以 i 为根的子树中，选自己(1) 或不选自己(0) 最多能选多少点。

设当前点为 u ，它的儿子们为 v ，显然转移方程为

主意第二个方程，点 u 不选时，它的儿子也可以不选，所以要取 \max

然后，就切了。。。

int f[MAXN][2];

void dfs(int u, int fa)
{
    f[u][1] = 1;
    f[u][0] = 0;
    for(int k=head[u];k;k=map[k].next)
    {
        int v = map[k].to;
        if(v == fa) continue;
        dfs(v,u);
        f[u][1] += f[v][0];
        f[u][0] += max(f[v][1],f[v][0]);
    }
}

int main(void)
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin >> u >> v;
        add(u,v);   add(v,u);
    }
    dfs(1,0);
    cout << max(f[1][1],f[1][0]) << "\n";
    return 0;
}

经典：

传送门

void dfs(int u)
{
    if(head[u] == -1)   //没有儿子 
    {
        dp[u][0] = 0;
        dp[u][1] = c[u];
        return;
    }
    dp[u][1] = c[u];
    for(int k=head[u];k!=-1;k=tree[k].next)
    {
        int v = tree[k].to;
        dfs(v);
        dp[u][0] += max(dp[v][0],dp[v][1]); //不选上司，儿子可选可不选，挑个大的 
        dp[u][1] += dp[v][0];               //选了父亲，儿子不能选 
    }
    return;
}

int main()
{
    memset(head,-1,sizeof(head));   //我也不清楚为什么要赋 -1 但赋 0 就错
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> c[i];
        num += i;
    }
    for(int i=1;i<=n;i++)
    {
        cin >> l >> k;
        num -= l;   //找出树根 
        add(l,k);
    }
    dfs(num);       //从树根开始dp
    cout << max(dp[num][0],dp[num][1]) << endl;
    return 0;
}

提高：

传送门

首先，十分感谢 HZW 奆老对我的帮助。

然后，让我们来分析一下本题

根据题意，我们需要开二维数组来记录每个节点相关的三个状态

即：

    因为 u 被父节点覆盖时，v 节点本身和其子节点的状态无需考虑，取最优值。

2. f [ 1 ] [ u ] += min( f [ 1 ] [ v ] , f [ 2 ] [ v ] , f [ 0 ] [ v ] );

   同上，不过也要将 v 节点的父节点考虑进去，因为其父节点就是 u 所以也要考虑它的值。

3. f [ 2 ] [ u ] += min( f [ 1 ] [ v ] , f [ 2 ] [ v ] );

   同上，u 的子节点的花费由 v 或其子节点推出。

但是！

仔细一想，事情好像并没有这么简单，

由于 u 可能有许多子节点，所有子节点的最优值之和才是 f [ 2 ] [ u ]

所以要进行判断，如果有一个 v 节点的值比其子节点要优，则将其加入

反之，加入 f [ 2 ] [ v ]

还没完，

由于 u 必由一个子节点所覆盖，

所以当出现所有子节点最优值都是 f [ 2 ] [ v ] 时，

则要由一个与 f [ 2 ] [ v ] 差最小的 v 替代 f [ 2 ] [ v ] ，

由于之前已取了所有的 f [ 2 ] [ v ] ，所以只要将差值记录并加入即可。

int val[MAXN];
int f[3][MAXN];

void dp(int u,int fa)
{
    f[1][u] = val[u];
    f[0][u] = f[2][u] = 0;
    int x = 0x3f3f3f3f;
    int flag = 0;
    for(int k=head[u];k;k=tree[k].next)
    {
        int v = tree[k].to;
        if(v == fa) continue;
        dp(v,u);
        f[0][u] += min(f[2][v],f[1][v]);
        f[1][u] += min(min(f[0][v],f[1][v]),f[2][v]);
        if(f[1][v] < f[2][v])   flag = 1;
        else    x = min(x,f[1][v]-f[2][v]);
        f[2][u] += min(f[1][v],f[2][v]);
    }
    if(!flag)   f[2][u] += x;
}

int main(void) 
{
    cin >> n;
    for(int i=1,u,w,m;i<=n;i++)
    {
        cin >> u >> w >> m;
        val[u] = w;
        for(int j=1,v;j<=m;j++)
        {
            cin >> v;
            add(u,v);   add(v,u); 
        }
    }
    dp(1,-1);
    cout << min(f[1][1],f[2][1]);
    return 0;
}

鸡掰：

传送门

这个题，真恶心

恶心恶心，真恶心，再这么恶心要哭了哦~~~

特别要注意边界问题

不要和我一样心态爆炸边打代码边大喊 F*K ！

好吧好吧，进入正题

这是一个森林，不好 DP （虽然有大佬直接DP的）

所以，

先转成二叉树（虚点 + 左儿子右兄弟）

然后，方程就好想了

再结合记忆化实现

struct node{
    int L,R;
    int w;
    node(){L = R = -1;}
}tree[MAXN];

int DP(int u, int k)
{
    if(k==0 || u==-1)   return 0;
    if(f[u][k] != 0)    return f[u][k];
    f[u][k] = max(f[u][k],DP(tree[u].R,k));
    for(int i=0;i<k;i++)
        f[u][k] = max(f[u][k],DP(tree[u].L,i)+DP(tree[u].R,k-1-i)+tree[u].w);
    return f[u][k];
}

int main(void)
{
    cin >> n >> m;
    for(int i=1,u,W;i<=n;i++)
    {
        cin >> u >> W;  //输入时转二叉树
        tree[i].R = tree[u].L;
        tree[u].L = i;
        tree[i].w = W;
    }
    cout << DP(0,m+1);
    return 0;
}

图P：

传送门

图上 DP

要把状态转移到 n 上，因为图可能不连通

由于有双向边，所以当 u 的状态被 fa 更新时，还要继续遍历 u

void dfs(int u, int fa, int minn)
{
    int flag = 1;
    minn = min(minn,a[u]);
    if(minn < m[u])
    {
        flag = 0;
        m[u] = minn;
    }
    f[u] = max(f[u],a[u]-m[u]);
    if(f[u] < f[fa])    //更新 u，并继续搜 u
    {
        f[u] = f[fa];
        flag = 0;
    }
    if(flag)    return;
    for(int k=head[u];k;k=map[k].next)
        dfs(map[k].to,u,minn);
}

int main(void)
{
    cin >> n >> r;
    memset(m,0x3f,sizeof m);
    for(int i=1;i<=n;i++)
        cin >> a[i];
    for(int i=1;i<=r;i++)
    {
        int u,v,f;
        cin >> u >> v >> f;
        add(u,v);
        if(f == 2)  add(v,u);
    }
    dfs(1,0,INF);
    cout << f[n];
    return 0;
}

贪心：

传送门

树 P 的题，用贪心做的，思路很好，记一下

但是这样有点不妥，显然点数越加越多，中间缺少了涂色的过程，所以每次转移完后要涂一次色。则方程就变成了这样：

其中为防止出现负数要与 0 取 max ，由于每次都减掉了 mid ，所以 f[i] 可以理解为以 i 为根的子树中涂了 mid 个点后还剩多少点 ，所以如果 f[1] = 0 ，则可行。

void dfs(int u, int fa, int mid)
{
    int sum = 0;
    for(int k=head[u];k;k=map[k].next)
    {
        int v = map[k].to;
        if(v == fa) continue;
        dfs(v,u,mid);
        sum += f[v]+1;
    }
    f[u] = max(0,sum-mid);
}

bool check(int mid)
{
    memset(f,0,sizeof f);
    dfs(1,0,mid);
    if(f[1] == 0) return 1;
    else          return 0;
}

int main(void)
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin >> u >> v;
        add(u,v);   add(v,u);
    }
    int L = 0;
    int R = n;
    while(L <= R)
    {
        int mid = (L+R)>>1;
        if(check(mid)) R = mid-1;
        else           L = mid+1;
    }
    cout << L;
    return 0;
}

递推：

传送门

是的，有时候树形 DP 要结合容斥来递推求解。

以样例为例子，我们可以一遍 DFS 求出点 1 的不方便程度，然后我们计算点 3 的值，经过思考我发现，点 3 的值其实是可以由点 1 转移的，因为从点 1 改成点 3 ，以点 3 为根的子树（包括点 3 ）都少走了 1 到 3 的路程，而其他点都要多走这一段路，由此得出转移方程：