P1270 【“访问”美术馆】

$\large{\text{一千个Oier程序中有一千种树形DP}}$

思路都差不多的，但是每个人都有自己的状态定义与转移

不妨定义$dp[i][j]$表示，在$i$子树内，偷$j$张画，且不考虑根到$i$父节点路径代价的最短时间

$a[i]$表示$i$与其父节点的距离

$d[i]$表示$i$到根节点的距离

不难想出转移

$\large{dp[i][j]=min\left\{dp[son1][k]+dp[son2][j-k]+dis[x]\right\}}$

统计答案

枚举每个节点选几个，如果$dp[i][j]+d[i]-a[i]<=s$，更新答案

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int size[],s,cnt,a[],v[],e[][],dp[][],ans,d[];

void init(int x)

{

    int t,to;

    if(scanf("%d%d",&t,&to)!=)

        return;

    d[x]+=*t,a[x]=*t,dp[x][]=;

    if(to)

        v[x]=to;

    else

    {

        d[++cnt]=d[x],init(e[x][]=cnt);

        d[++cnt]=d[x],init(e[x][]=cnt);

    }

}

void dfs(int x)

{

    if(!x)

        return;

    dfs(e[x][]),dfs(e[x][]);

    size[x]=v[x]+size[e[x][]]+size[e[x][]];

    if(v[x])

        for(int i=;i<=v[x];i++)

            dp[x][i]=a[x]+dp[x][]+*i;

    else

        for(int i=;i<=size[x];i++)

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

                dp[x][i]=min(dp[x][i],dp[e[x][]][j]+dp[e[x][]][i-j]+a[x]);

}

int main()

{

    scanf("%d",&s);

    memset(dp,0x3f,sizeof(dp));

    init(++cnt);

    dfs();

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

        for(int j=;j<=size[i];j++)

            if(dp[i][j]+d[i]-a[i]<s)

                ans=max(ans,j);

    printf("%d\n",ans);

    return ;

}

巴特西

P1270 【“访问”美术馆】

最新文章

热门文章