（感觉洛谷上题面那一小段中文根本看不懂啊，好多条件都没讲，直接就是安装也要一个时间啊，，，明明不止啊！还好有百度翻译。。。。。。）

题意：一棵树，一开始在1号节点（root），边权都为1，每个点有点权，要最小化max(点权+到达时间） <---所有点的

首先这看起来就是一道DP题，但是根据直觉，，，应该跟贪心挂钩，因为感觉耗时久的要先去是吧

但是我们发现并不能这么弄，因为去一棵子树就要走完它，这个时候再去别的树的时候可能已经很晚了，所以就不一定优了

不过我们可以发现，从一个点出发，去节点的顺序就决定了答案

于是我们考虑排序

但是节点太多比较难以分析，因此我们先以两个儿子为例分析。

f[i]代表以i为根的最大时长，

于是目的就是最小化f[1],size[i]代表遍历这个点要多久，

因为要遍历完这个子树才可以去另一棵，于是就有转移方程：

f[i]=max(f[a],f[b] + size[a] + 2),其中a，b为两棵子树，+2是去a的那条边来回的时间，这个是先去a的，

f[i]=max(f[b],f[a] + size[b] + 2),然后就是最小化这4个式子中的最大值，

PS:等等，，，貌似是f[a]+1????，懒得改了，，，大家自行脑补成f[a]+1吧，不影响结果

于是先按照国王游戏里面的方法来推导一下:

首先设先去a比较优，

那么有max(f[a],f[b] + size[a] + 2) < max(f[b],f[a] + size[b] + 2)

因为f[a] + size[b] + 2 > f[a],f[b] + size[a] + 2 > f[b],

所以这4个式子的最大值不可能会是f[a] or f[b],

所以要使得等式成立就只能寄希望于

f[b] + size[a] + 2 < f[a] + size[b] + 2

所以以这个为条件排序即可

各种细节QAQ调了好久

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 501000

 #define getchar() *o++

 #define LL long long

 char READ[],*o=READ;

 int n,ans;

 int cost[AC],size[AC];

 int date[AC * ],Next[AC * ],Head[AC],tot;

 struct point{

     int size;

     LL f;

 }p[AC];

 LL f[AC];

 inline int read()

 {

     int x=;char c=getchar();

     while(c > '' || c < '') c=getchar();

     while(c >= '' && c <= '') x=x*+c-'',c=getchar();

     return x;

 }

 inline void add(int f,int w)

 {

     date[++tot]=w,Next[tot]=Head[f],Head[f]=tot;

     date[++tot]=f,Next[tot]=Head[w],Head[w]=tot;

 }

 inline bool cmp(point a,point b)

 {

     return b.f + a.size < a.f + b.size;

 }

 void pre()

 {

     R a,b;

     n=read();

     for(R i=;i<=n;i++) cost[i]=read();

     for(R i=;i<n;i++)

     {

         a=read(),b=read();

         add(a,b);

     }

 }

 void DFS(int x,int fa)//还是要传father，不然的话下面加入队列的部分就判断不了了，因为这时下面都已经访问过了

 {

     int now,tot=;

     if(x != ) f[x] = cost[x];//至少自己要装啊,但是注意第一个是最后装的

     for(R i=Head[x]; i ;i=Next[i])

     {

         now=date[i];

         if(now == fa) continue;

         DFS(now,x);

     }

     for(R i=Head[x]; i ;i=Next[i])

     {

         now=date[i];

         if(now != fa)

             p[++tot]=(point) {size[now],f[now]};//不能在上面加，因为一旦下一次调用了DFS，队列里就乱了

     }

     sort(p+,p+tot+,cmp);

     for(R i=;i<=tot;i++)

     {

         f[x]=max(f[x],p[i].f + size[x] + );

         size[x] += p[i].size + ;//反正这样也是统计了一样的东西

     }

 }

 int main()

 {

     freopen("in.in","r",stdin);

     fread(READ,,,stdin);

     pre();

     DFS(,);

     printf("%lld\n",max(f[],(LL)(n *  -  + cost[])));

     fclose(stdin);

     return ;

 }

巴特西

[POI2014]FAR-FarmCraft 树形DP + 贪心思想

[POI2014]FAR-FarmCraft

最新文章

热门文章