访问美术馆题解 树形DP

· · 题解

题目传送门

前置知识

树形DP。

题意描述

树形DP

一看是一棵树，这显然又是一个DP，那么就树形DP。

我们得知，走了这条边进去，必要走这条边出来。不妨在建树时，对每个边权乘上2。

首先这题的输入格式跟一般题目不太一样，我们先要学会输入。

我们递归进行处理。

每次若第二个数是0，我们递归2次进行加点。

否则给他加权。

建边函数。

void build(ll fa){
    n++;
    ll u=0,v=0;
    rd(u);rd(v);
    add(fa,n,u*2);
    ll aa=n;
    if(v==0) build(aa),build(aa);
    else a[n]=v;
}

主函数调用部分。

    if(v==0) n=2,add(1,2,u*2),build(2),build(2);
    else add(1,2,u*2),n=2,a[2]=v;

然后我们一看，感觉典型的DP问题。（废话）

我们设 f_{i,j} 为走到 i 节点用了 j 单位时间并走回来的最大收益。

因为每个节点若有儿子必只有两个（由题得），我们可以得到转移方程。

f_{x,j}=max{f_{x,j},f_{x,j-k}+f_{es[i].t,k-es[i].va}}

如果我们在叶子节点时，用点权更新 f 数组。

for(ll i=5;i<=m;i++) f[x][i]=min(a[x],f[x][i-5]+1);

我们就可以从根节点开始递归处理，然后枚举 j 和 k，不断更新得出答案。

答案有注意点，是 f_{1,m-1}，他不能和警察同时。

/*
***
还要继续努力
成为一名烤咕学家哦
***
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=605;
ll n,m,tot,hd[N],vst[N],cnt,a[N],f[N][N],ans;
struct edge{ll t,nxt,va;}es[N<<2];
template <typename T> void rd(T &x){
    ll fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
void wr(ll x){
    if(x<0) x=-x,putchar('-');
    if(x<10) putchar(x+'0');
    if(x>9) wr(x/10),putchar(x%10+'0');
}
void add(ll u,ll v,ll w){
    es[++tot]=(edge){v,hd[u],w},hd[u]=tot;
}
void build(ll fa){
    n++;
    ll u=0,v=0;
    rd(u);rd(v);
    add(fa,n,u*2);
    ll aa=n;
    if(v==0) build(aa),build(aa);
    else a[n]=v;
}
void dfs(ll x){
    vst[x]=1;
    if(a[x]!=0){
        for(ll i=5;i<=m;i++) f[x][i]=min(a[x],f[x][i-5]+1);
        return ;
    }
    for(ll i=hd[x];i;i=es[i].nxt)
        if(!vst[es[i].t]){
            dfs(es[i].t);
            for(ll j=m;j>=es[i].va;j--)
                for(ll k=es[i].va;k<=j;k++)
                    f[x][j]=max(f[x][j],f[x][j-k]+f[es[i].t][k-es[i].va]);
        }
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(m);
    ll u=0,v=0;
    rd(u);rd(v);
    if(v==0) n=2,add(1,2,u*2),build(2),build(2);
    else add(1,2,u*2),n=2,a[2]=v;
    dfs(1);
    wr(f[1][m-1]);puts("");
    return 0;
}

然后你就A了一道蓝题QAQ。