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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3829][Poi2014]FarmCraft  

2015-01-28 11:05:42|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3829: [Poi2014]FarmCraft

搞了一节课
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 500000 + 100;
typedef long long ll;
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{
int d;Point *next;
Point(){next = NULL;}
void push(int a){
Point *l = new Point;
l->d = a;
l->next = next;next = l;
}
}point[N];
int n,data[N],list[N],size[N],fa[N];ll f[N];
bool cmp(int a,int b){return f[a] > f[b];}
void dfs(int x = 1){
size[x] = 1;
for(Point *i = point[x].next;i!=NULL;i=i->next)
if(fa[x]!=i->d){
fa[i->d] = x;
dfs(i->d);//f[i->d]--;
size[x] += size[i->d];
}
list[0] = 0;for(Point *i = point[x].next;i!=NULL;i=i->next)if(fa[x]!=i->d)list[++list[0]] = i->d;
sort(list+1,list+1+list[0],cmp);
int tmp = 1;
for(int i=list[0];i;i--){
f[x] = max(f[x],f[list[i]] - tmp);
tmp += size[list[i]]*2;
}
if(x!=1)f[x] = max(f[x],(ll)data[x]-(size[x]-1)*2);
else f[x] = max(f[x],(ll)data[x]);
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;
n = scan();
for(i=1;i<=n;i++)data[i] = scan();
for(i=1;i<n;i++){
a = scan();b = scan();
point[a].push(b);
point[b].push(a);
}
dfs(1);
printf("%lld",f[1]+(n-1)*2);
return 0;
}

题解:
树形Dp
f[i]表示遍历完i的子树到回这个点后安装完成还需要的时间
然后对于一个点显然要先去f[]值大的地方,对于f[]值相同的先去size小的
刚刚才想起来f[]相同的情况……代码里没写也能A- -|| 懒得改了
  评论这张
 
阅读(29)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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