SSLOJ2570 2016年提高组模拟题(20161111) 幸福的道路(race)-白红宇的个人博客

SSLOJ2570 2016年提高组模拟题(20161111) 幸福的道路(race)

发布日期：2021-05-07 09:40:58 浏览次数：21 分类：精选文章

本文共 1856 字，大约阅读时间需要 6 分钟。

Description

小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图.他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线.他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M.他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)?现在，他们把这个艰巨的任务交给你了!

Input

第一行包含两个整数N, M(M<=10^9).第二至第N行,每行两个数字Fi , Di, 第i行表示第i个节点的父亲是Fi,且道路的幸福值是Di.

Output

最长的连续锻炼天数

思路

~~啊long longTLE int AC,BZOJ2500*^*%$%(^~~

其实是树状dp+单调队列。

首先看树状dp，我们先一步dfs，求出每个点只能往下走的最长路和次长路及最长路的下一个位置。

再来一次dfs，这里我们处理能够从上面走另一条路的情况。我们使用其父节点的最长路，如果其最长路经过了该节点则使用次长路，对最长路进行更新。

接下来是单调队列，每次入队一个，然后排出不符合条件的情况，具体使用2个单调队列，一个最大一个最小，出队的是距离现在位置更远的那一个（正确性显然），然后求长度最大值，输出，完事

code:

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        using namespace std;int n,a[1000101][3],tot=1,m,fa,fa2,u[1000101],head[1000101],to[1000101],net[1000101],l,r;int max(int x,int y){ if (x
         
          a[x][0]) { a[x][1]=a[x][0]; a[x][2]=to[i]; a[x][0]=a[to[i]][0]+u[i]; } else if (a[to[i]][0]+u[i]>a[x][1]) { a[x][1]=a[to[i]][0]+u[i]; } } return;}int len;void dp2(int x,int fa,int w){ len=(x==a[fa][2]?a[fa][1]+w:a[fa][0]+w); if (len>a[x][0]) { a[x][1]=a[x][0]; a[x][2]=fa; a[x][0]=len; } else { if (len>a[x][1]) a[x][1]=len; } for (int i=head[x];i;i=net[i]) { dp2(to[i],x,u[i]); } return;}void wr(int x){ if (x>9) wr(x/10); putchar(x%10^48);}int xx[1000101],yy[1000101],lx,rx,ly,ry,ans=1,last=1;int check(){ lx=ly=1; for (int i=1;i<=n;i++) { while (lx<=rx&&a[xx[rx]][0]>=a[i][0]) rx--; rx++; xx[rx]=i; while (ly<=ry&&a[yy[ry]][0]<=a[i][0]) ry--; ry++; yy[ry]=i; while (a[yy[ly]][0]>a[xx[lx]][0]+m) { if (yy[ly]>xx[lx]) last=xx[lx++]+1; else last=yy[ly++]+1; } ans=max(ans,i-last+1); } return ans;}int main(){ read(n),read(m); for (int i=2;i<=n;i++) { read(fa),read(fa2); add(fa,i,fa2); } dp1(1); dp2(1,0,0); wr(check()); return 0;}

上一篇：P1462 通往奥格瑞玛的道路

下一篇：P2700 逐个击破

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

Description

Input

Output

思路

发表评论

最新留言

关于作者

推荐文章