「Luogu P4438」[HNOI/AHOI2018]道路

发表于 |
字数统计: 766 | 阅读时长 ≈ 3

给你一颗有$2n-1$个节点的树，这一棵树的非叶节点均有两个儿子，左儿子与它连红边，右儿子与它连绿边，定义节点$i$的不便利值为
$c_i\cdot(a_i+x)\cdot(b_i+y)$
其中$x$表示根节点到节点$i$的未加粗红边数量，$y$表示根节点到节点$i$的未加粗绿边数量。
求加粗边数量为$n-1$的所有叶节点的不便利值。

链接

Luogu P4438

题解

一道比较好的树形dp题。
将每一个城市标号$1$到$n-1$，乡村标号$n$到$2n-1$，设$dp[i][j][k]$表示标号后的$i$号节点到根节点要走过$j$条没有翻修的公路和$k$条没有翻修的铁路最小的不便利值。
设$l[i]$指的是通过公路连接$i$号结点的城市或乡村，$r[i]$指的是通过铁路连接$i$号结点的城市或乡村，那么
如果$i$是乡村，直接暴力算不便利值即可，即
$dp[i][j][k]=c_i\cdot(a_i+j)\cdot(b_i+k)$
如果$i$是城市，因为最多翻修$n-1$条路，所以考虑对通向每一个城市的公路或铁路进行翻修。
翻修通往城市$i$的公路的不便利值是$dp[l_i][j+1][k]+dp[r_i[j][k]$（因为通向$i$的铁路没翻修），铁路同理，即
$dp[i][j][k]=\min(dp[l_i][j+1][k]+dp[r_i[j][k],dp[l_i[j][k]+dp[r_i][j][k+1])$
所以就得到了转移方程。
最后善意的提醒一句，本题卡空间，大佬们可以将$dp$的一维改成$dfn$，蒟蒻不会，只能暴力

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll MAXN=4e4+51;
ll cnt;
ll l[MAXN],r[MAXN],lx[MAXN],rx[MAXN];
ll x[MAXN],y[MAXN],z[MAXN];
ll dp[MAXN][41][41];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void dfs(ll node)
{
    if(node>=cnt)
    {
        return;
    }
    lx[l[node]]=lx[node]+1,lx[r[node]]=lx[node];
    rx[r[node]]=rx[node]+1,rx[l[node]]=rx[node];
    dfs(l[node]);
    dfs(r[node]);
}
inline void ddp(ll node)
{
    ll lc,rc;
    if(node>=cnt)
    {
        for(register int i=0;i<=lx[node];i++)
        {
            for(register int j=0;j<=rx[node];j++)
            {
                dp[node][i][j]=1ll*(x[node]+i)*(y[node]+j)*z[node];
            }
        }
        return;
    }
    else
    {
        ddp(l[node]);
        ddp(r[node]);
        for(register int i=0;i<=lx[node];i++)
        {
            for(register int j=0;j<=rx[node];j++)
            {
                lc=dp[l[node]][i][j]+dp[r[node]][i][j+1];
                rc=dp[r[node]][i][j]+dp[l[node]][i+1][j];
                dp[node][i][j]=min(lc,rc);
            }
        }
    }
}
int main()
{
    cnt=read();
    for(register int i=1;i<cnt;i++)
    {
        l[i]=read(),r[i]=read();
        l[i]=l[i]<0?-l[i]+cnt-1:l[i],r[i]=r[i]<0?-r[i]+cnt-1:r[i];
    }
    for(register int i=1;i<=cnt;i++)
    {
        x[i+cnt-1]=read(),y[i+cnt-1]=read(),z[i+cnt-1]=read();
    }
    dfs(1),ddp(1);
    printf("%lld",dp[1][0][0]);
}