太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。
皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状,某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。
可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。
帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。
题解
多考虑一步,子节点都安全的情况下,都不选子节点,而选父节点最优 ,因此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;
}