注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1217][HNOI2003]消防局的设立  

2015-03-24 20:16:52|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1217: [HNOI2003]消防局的设立

一开始想错了QAQ以为是傻逼题
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 1E6+10;
int n,m,ans,fa[N];
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
struct Point{
Point(){next=NULL;}
int d;Point *next;
void push(int a){
Point *l = new Point;
l->d = a;l->next = next;
next= l;
}
}point[N];
int f[N][5];
void dfs(int x=1){
bool son=0;
int sum[2]={};
f[x][1]=f[x][2]=1e9;
for(Point *i = point[x].next;i;i=i->next)
if(i->d!=fa[x]){
son=1;
fa[i->d]=x;
dfs(i->d);
f[x][0]+=f[i->d][4];
f[x][3]+=f[i->d][2];
f[x][4]+=f[i->d][3];
}
for(Point *i = point[x].next;i;i=i->next)
if(i->d!=fa[x]){
f[x][1]=min(f[x][1],f[x][4]-f[i->d][3]+f[i->d][0]);
f[x][2]=min(f[x][2],f[x][3]-f[i->d][2]+f[i->d][1]);
}
f[x][0]+=1;
for(int i=1;i<=4;i++)f[x][i]=min(f[x][i],f[x][i-1]);
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a;
n = scan();
for(i=2;i<=n;i++){
a=scan();
point[i].push(a);
point[a].push(i);
}
dfs();
printf("%d\n",f[1][2]);
return 0;
}

题解:
树形DP
f[i][j] 表示以i点为根的子树中,距根最远点的距离是j 
为了方便,我们使f[i][j]=min(f[i][0..j])  (因为有f[i][j]>=f[i][j+1])
f[i][0]=(sigma f[i->d][4]) +1 
f[i][1]=(sigma f[i->d][3]) +min(-f[i->d][3]+f[i->d][0]) 
f[i][2]=(sigma f[i->d][2]) +min(-f[i->d][2]+f[i->d][1]) 
f[i][3]=sigma f[i->d][2] 
f[i][4]=sigma f[i->d][3]
i->d表示i的儿子……
  评论这张
 
阅读(457)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017