- 小胖守皇宫
- 2020-03-07 10:28:56 @
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
//树形dp
//通常使用树形结构树上dfs 用单独维度表示当前节点状态
//皇宫守卫/小胖守皇宫
//关键 使用三个0 1 2表示状态 (节点放 节点父亲放 节点子孙放)
//注意状态转移技巧 对于f[u][1]
//f[u][0]父节点监视 f[u][1]子节点监视 f[u][0]自己放置
//此时有大量重复 所以修正为
//f[u][0] 父节点监视 节点本身无 (可能存在子节点监视)
//f[u][1] 子节点监视 节点本身无 (可能存在父节点监视)
//f[u][2] 节点本身有
//以上f[u][0] f[u][1]仍然有重复 但可用计算技巧性取得min属性
//由于要求attr为min 可以重复 不影响
//通过这个重复可以快速计算出f[u][1] = min(f[u][0] - ... + ...)
const int N = 2000;
const long long inf = 0x7fffffff;
long long f[N][3];
int h[N],e[N],ne[N];
int idx = 0;
int n;
int fa[N];
long long w[N];
void init(){
idx = 0;
memset(h,-1,sizeof h);
}
void add(int a,int b){
e[idx] = b,ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int u){
f[u][1] = inf;
f[u][0] = 0;
f[u][2] = w[u];
for(int j=h[u];j!=-1;j=ne[j]){
int v = e[j];
dfs(v);
//自给自足
f[u][0] += min(f[v][1],f[v][2]);
//不需自给自足 有重叠不影响
f[u][2] += min(min(f[v][0],f[v][1]),f[v][2]);
//最麻烦情况 从子节点中选最小的 此时可能不止一个子节点有
//而且当前节点父节点可能有 而且未被选中子节点需要自给自足
// f[u][1] = min(f[u][1],f[u][0] - min(f[v][1],f[v][2]) + f[v][2]);
//这里写错了 必须f[u][0]最终结果得到才可以计算f[u][1]
}
for(int j=h[u];j!=-1;j=ne[j]){
int v = e[j];
f[u][1] = min(f[u][1],f[u][0]-min(f[v][1],f[v][2])+f[v][2]);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
int l,k,r;
init();
for(int i=0;i<n;i++){
cin>>l>>w[l]>>k;
for(int i=0;i<k;i++){
cin>>r;
add(l,r);
fa[r] = l;
}
}
int root = 1;
while(fa[root]) root++;
dfs(root);
//树根节点不可能有f[u][0]
cout<<min(f[root][1],f[root][2])<<endl;
return 0;
}
第一个测试点通过,其余测试点wa
loj上可以A掉
0 条评论
目前还没有评论...