太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。

皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状,某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。

帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。

🔗[LOJ 10157] 皇宫守卫

题解

多考虑一步,子节点都安全的情况下,都不选子节点,而选父节点最优 ,因此DP得多开一度
dp[i][0] 当前点被覆盖,但不选的最小代价
dp[i][1] 选这个点的最小代价
dp[i][2] 为被覆盖且不选该点的最小代价(该点的子节点都被覆盖,自身未被覆盖,给父节点多一个选择机会)

dp[i][1] = min(dp[i][0],dp[i][1],dp[i][2])
dp[i][0] = min(dp[i][1],dp[i][0])
dp[i][2] = min(dp[i][1],dp[i][0]) + \sum_i min(dp[i][1] - min(dp[i][0],dp[i][1]))
保证有一个子节点被选的最优情况

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxd = 1505;
int fa[maxd],arr[maxd],n,a,b,c,ans;
int dp[maxd][3];
void dfs(int x)
{
    dp[x][1] = arr[x];
    int k = 1e8;
    for(int i=1;i<=n;i++)
    {
        if(fa[i]!=x) continue;
        dfs(i);
        dp[x][1] += min(dp[i][0],min(dp[i][1],dp[i][2]));
        dp[x][2] += min(dp[i][0],dp[i][1]);
        dp[x][0] += min(dp[i][0],dp[i][1]);
        k = min(k,dp[i][1] - min(dp[i][0],dp[i][1]));
    }
    dp[x][0] += k;
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        scanf("%d %d",&arr[a],&b);
        for(int j=1;j<=b;j++)
        {
            scanf("%d",&c);
            fa[c] = a;
        }
    }
    int root = 1;
    //for(int i=1;i<=n;i++) printf("%d ",arr[i]);
    while(fa[root]) root = fa[root];
    dfs(root);
    // printf("%d %d",dp[2][0],dp[2][1]);
    if(dp[root][0]!=0) printf("%d",min(dp[root][0],dp[root][1]));
    else printf("%d",dp[root][1]);
    return 0;
}