这题还是很简单的
设$dp[status: 0/1/2][i]$为第i个点，状态为$status$时的最小代价
| 状态 |
含义 |
转移方程 |
| 0 |
i点被父亲覆盖 |
$dp[0][i]=\sum\min(dp[1][son],dp[2][son])$ |
| 1 |
i点被自己覆盖 |
$dp[1][i]=v[i]+\sum\min(dp[0][son],dp[1][son],dp[2][son])$ |
| 2 |
i点被儿子覆盖 |
$dp[2][i]=\min(dp[1][soni]+\sum_{sonj \ne soni}\min(dp[1][sonj],dp[2][sonj]))$ |
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,l,r) for (int i=(l);i<=(r);++i)
#define REP(i,l,r) for (int i=(l);i<(r);++i)
#define RFOR(i,l,r) for (int i=(l);i>=(r);--i)
#define RREP(i,l,r) for (int i=(l);i>(r);--i)
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3fLL;
inline void readi(int &p){
p=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+c-'0';c=getchar();}
p=f*p;
}
inline void readl(ll &p){
p=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+c-'0';c=getchar();}
p=f*p;
}
struct node{
int Next,y;
}Pth[3005];
int head[1505],cnt;
inline void add(int x,int y){
cnt++;
Pth[cnt].Next=head[x];
Pth[cnt].y=y;
head[x]=cnt;
}
int n,k[1505],dp[3][1505];
void dfs(int x,int prv){
int min_cho=INF;
for (int i=head[x];i;i=Pth[i].Next){
int y=Pth[i].y;
if (y==prv) continue;
dfs(y,x);
dp[0][x]+=min(dp[1][y],dp[2][y]);
dp[1][x]+=min(dp[1][y],min(dp[2][y],dp[0][y]));
dp[2][x]+=min(dp[1][y],dp[2][y]);
min_cho=min(min_cho,dp[1][y]-min(dp[1][y],dp[2][y]));
}
dp[1][x]+=k[x];
dp[2][x]+=min_cho;
}
int main(){
readi(n);
FOR(i,1,n){
int x; readi(x);
readi(k[x]);
int m; readi(m);
FOR(j,1,m){
int y; readi(y);
add(x,y); add(y,x);
}
}
dfs(1,-1);
printf("%d\n",min(dp[1][1],dp[2][1]));
return 0;
}
|
第一题的升级版，状态多了一些，同时用一些技巧减少代码量
设$dp[status: 0/1/2/3/4][i]$为第i个点，状态为$status$时的最小代价
| 状态 |
含义 |
转移方程 |
| 0 |
覆盖节点i向上2层 |
$dp[0][i]=1+\sum dp[4][son]$ |
| 1 |
覆盖节点i向上1层 |
$dp[1][i]=\min(dp[0][soni]+\sum_{sonj \ne soni}{dp[3][sonj]})$ |
| 2 |
覆盖节点i向上0层 |
$dp[2][i]=\min(dp[1][soni]+\sum_{sonj \ne soni}{dp[2][sonj]})$ |
| 3 |
覆盖节点i向上-1层 |
$dp[3][i]=\sum dp[2][son]$ |
| 4 |
覆盖节点i向上-2层 |
$dp[4][i]=\sum dp[3][son]$ |
其中，覆盖到某层的意思是在这棵子树中这一层和其以下层的所有点都被消防站覆盖到。比如，
“覆盖到从节点i向上1层”指的是“以节点i为根的整棵子树和i的父亲都被覆盖(不包含i的父亲的其他子树)”，
“覆盖到从节点i向上-1层”指的是“节点i的所有儿子和它们的子孙都被覆盖”。
在这五个状态中，上面的状态是包含下面的状态的。比如，如果能覆盖到节点i向上2层，则一定能覆盖到节点i向上1层。所以，有
$dp[0][i]\ge dp[1][i]\ge dp[2][i]\ge dp[3][i]\ge dp[4][i]$
状态转移
$dp[0][i]=1+\sum dp[4][son]$
因为i可以覆盖到向上2层，所以它自己必须是消防站。此时，它可以覆盖到所有儿子和孙子，因此儿子的状态可以是$dp[0-4][son]$中的任意一种情况。但因为我们需要使得消防站个数最少，所以取$dp[4][son]$。
$dp[1][i]=\min(dp[0][soni]+\sum_{sonj \ne soni}{dp[3][sonj]})$
因为i可以覆盖到向上1层，所以存在两种情况：要么恰好覆盖到i上面的1层，要么向上覆盖2层。
如果恰好覆盖到向上1层，那么i的至少一个儿子必须是消防站。其它儿子的状态可以是$dp[0-3][son]$中的任意一种。同样，因为要取消防站个数最小值，取$dp[3][son]$。
而如果向上覆盖两层，情况和$dp[0][i]$是一样的，取这两者最小值。
$dp[2][i]=\min(dp[1][soni]+\sum_{sonj \ne soni}{dp[2][sonj]})$
因为i可以覆盖到向上0层，所以要么恰好向上覆盖0层，要么向上覆盖1~2层。
如果向上覆盖0层，那么i的至少一个孙子必须是消防站，其它儿子的状态可以是$dp[0-2][son]$中的任意一种。取$dp[2][son]$。
而如果向上覆盖两层，情况和$dp[0][i]$和$dp[1][i]$是一样的，取这三者最小值。
$dp[3][i]=\sum dp[2][son]$
如果i恰好可以覆盖到向上-1层，即所有儿子被覆盖就可以。于是取$dp[2][son]$。其它情况和上面取最小值。
$dp[4][i]=\sum dp[3][son]$
如果i恰好可以覆盖到向上-2层，即所有孙子被覆盖就可以。取$dp[3][son]$。其它情况和上面取最小值。
最终目标
我们希望寻找当整棵树都被覆盖的时候的消防站最小值，于是需要覆盖到根的这一层，于是结果是$dp[2][1]$。
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,l,r) for (int i=(l);i<=(r);++i)
#define REP(i,l,r) for (int i=(l);i<(r);++i)
#define RFOR(i,l,r) for (int i=(l);i>=(r);--i)
#define RREP(i,l,r) for (int i=(l);i>(r);--i)
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3fLL;
inline void readi(int &p){
p=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+c-'0';c=getchar();}
p=f*p;
}
inline void readl(ll &p){
p=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+c-'0';c=getchar();}
p=f*p;
}
struct node{
int Next,y;
}Pth[2005];
int head[1005],cnt;
inline void add(int x,int y){
cnt++;
Pth[cnt].Next=head[x];
Pth[cnt].y=y;
head[x]=cnt;
}
int n,dp[5][1005];
void dfs(int x,int prv){
int F1=INF,F2=INF;
for (int i=head[x];i;i=Pth[i].Next){
int y=Pth[i].y;
if (y==prv) continue;
dfs(y,x);
dp[0][x]+=dp[4][y];
dp[1][x]+=dp[3][y]; F1=min(F1,dp[0][y]-dp[3][y]);
dp[2][x]+=dp[2][y]; F2=min(F2,dp[1][y]-dp[2][y]);
dp[3][x]+=dp[2][y];
dp[4][x]+=dp[3][y];
}
dp[0][x]++;
dp[1][x]+=F1;
dp[2][x]+=F2;
FOR(i,1,4) dp[i][x]=min(dp[i-1][x],dp[i][x]);
}
int main(){
readi(n);
FOR(i,2,n){
int x;
readi(x);
add(i,x); add(x,i);
}
dfs(1,-1);
cout<<dp[2][1]<<endl;
return 0;
}
|
同理可以处理距离>2时的情况了，只不过状态多一些，转移用for循环罢了
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/%E8%B7%9D%E7%A6%BB%E6%9C%89%E5%85%B3%E6%A0%91%E5%BD%A2dp/
