由于BlogCN的服务器不稳定,本站现已搬至http://tenpages.blog.cd/
本站尚未停止更新,但会逐步转移至上述网址.
[解法]
应该可以算是树龟的题目
先初始化一个数组f[],其中f[i]保存以第i个节点为根的半条毛毛虫最大是多少
(所谓半条毛毛虫就是从i向下可以延伸,但不向上延伸.样例数据的f[]存储结果如图3所示)
然后遍历一遍每个节点,计算以这个节点为中继站的,毛毛虫头和尾都是以这个节点为根的子树中的节点的最大的毛毛虫(...乱),最后找最大即可
[程序]
002 var
003 pre,last,son,num:array[1..650000]of longint;
004 firmax,secmax:array[1..300000]of longint;
005 b:array[1..300000]of boolean;
006 f:array[1..300000]of longint;
007 n,m,find:longint;
008 procedure Init;
009 var
010 i,t:longint;
011 tempi,tempj:longint;
012 procedure BuildEdge(b,e:longint);
013 begin
014 inc(t);
015 pre[t]:=last[b];
016 last[b]:=t;
017 son[t]:=e;
018 end;
019
020 function max(n1,n2:longint):longint;
021 begin
022 if n1>n2 then exit(n1);
023 exit(n2);
024 end;
025
026 procedure Build_F(v:longint);
027 var
028 pt,tot:longint;
029 begin
030 pt:=last[v]; tot:=0; f[v]:=1;
031 firmax[v]:=-1; secmax[v]:=-2;
032 while pt<>0 do begin
033 if b[son[pt]] then
034 begin
035 inc(tot);
036 b[son[pt]]:=false;
037 Build_F(son[pt]);
038 f[v]:=max(f[v],f[son[pt]]);
039 if f[son[pt]]>firmax[v] then
040 begin
041 secmax[v]:=firmax[v];
042 firmax[v]:=f[son[pt]];
043 end
044 else if f[son[pt]]>secmax[v] then
045 secmax[v]:=f[son[pt]];
046 end;
047 pt:=pre[pt];
048 end;
049 f[v]:=f[v]+tot;
050 inc(num[v],tot);
051 end;
052 begin
053 assign(input,'worm.in');
054 reset(input);
055 read(n,m);
056 t:=0;
057 fillchar(b,sizeof(b),true);
058 for i:=1 to m do begin
059 read(tempi,tempj);
060 BuildEdge(tempi,tempj);
061 BuildEdge(tempj,tempi);
062 end;
063 close(input);
064
065 b[1]:=false;
066 fillchar(num,sizeof(num),0);
067 Build_F(1); //预处理f数组;即求当该树以1节点为根时,从1到每个节点的(半条)毛毛虫的最大数,用f[i]保存
068 end;
069
070 procedure Main;
071 var
072 i,temp:longint;
073 begin
074 temp:=-1;
075 case num[1] of
076 0:temp:=1;
077 1:temp:=firmax[1]+1;
078 else temp:=firmax[1]+secmax[1]+num[1]-1;
079 end;
080 find:=temp;
081
082 for i:=2 to n do begin
083 case num[i] of
084 0:temp:=2;
085 1:temp:=firmax[i]+2;
086 else temp:=firmax[i]+secmax[i]+num[i];
087 end;
088 if temp>find then find:=temp;
089 end;
090 end;
091
092 procedure Print;
093 begin
094 assign(output,'worm.out');
095 rewrite(output);
096 writeln(find);
097 close(output);
098 end;
099 begin
100 Init;
101 Main;
102 Print;
103 end.
URAL1018 树型动规初步
巧克力
（文件名chocolate.pas/.c/.cpp,测试点时限1s）
试题描述
有一块n*m的矩形巧克力，准备将它切成n*m块。巧克力上共有n-1条横线和m-1条竖线，你每次可以沿着其中的一条横线或竖线将巧克力切开，无论切割的长短，沿着每条横线切一次的代价依次为y1，y2，…，yn-1，而沿竖线切割的代价依次为x1，x2，…，xm-1。例如，对于下图6*4的巧克力，我们先沿着三条横线切割，需要3刀，得到4条巧克力，然后再将这4条巧克力沿竖线切割，每条都需要5刀，则最终所花费的代价为y1+y2+y3+4*(x1+x2+x3+x4+x5)。
当然，上述简单切法不见得是最优切法，那么怎样切割该块巧克力，花费的代价最少呢？
输入数据
在文本文件chocolate.in中的第一行为两个整数n和m。
接下来n-1行，每行一个整数，分别代表x1，x2，…，xn-1。
接下来m-1行，每行一个整数，分别代表y1，y2，…，ym-1。
输出数据
在文本文件chocolate.out中输出一整数，为切割巧克力的最小代价。
样例输入
6 4
2
1
3
1
4
4
1
2
样例输出
42
测试数据范围
30%的数据，n<=100,m<=100
100%的数据，n<=10000，m<=10000
为期十天的『冬令营』终于结束了
这十天接触了许多新东西，比如连通分量，比如树龟，比如并查集，比如线段树。这些都是众牛们认为省选必备的东西。
断断续续的十天一转眼就过完了，而本来屈指可数的假期也见底儿了。距离省选越来越近，还有许多东西没有掌握透，还要好好研究。
鸭梨巨大，但是有鸭梨才会有冻梨。
强连通分量的Tarjan算法应用 
oi2008,题目名称blo
树形动归:基础题目:没有上司的舞会/二叉苹果树
并查集:银河英雄传说(Accepted)/Poi2008,题目名称pla
线段树:高级线段树(不理解),有一题是Ioi2005,题目名称游乐场过山车(mou);Ioi2009旅行家
动态规划的斜率优化:CEoi2004,题目名称锯木厂选址;还有相似的题目Ioi2009旅行家,它的dp优化方案跟这个比较象
最近发现了一个高级的物理沙盒，我个人感觉它和Mathematica可以起同样的作用（当然，在不同的领域）
在一个视频中发现的，前几天在Matrix上挖坟的时候又看到了这个视频，并且得知它的名字——Phun
感觉这个程序挺不错的，现在我得到的比较新的版本是5.2.8吧好像，是个免费的；而收费程式的名字唤作Aldogoo，在这个程式中，有一个更高级的工具画笔，几乎可以替代其他所有工具的作用。
幸运的是，这个收费的正式版有大约15小时的试用期
Noi2002第一试
银河英雄传说
【问题描述】
公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。
宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。
杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。
然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监瑞脑消金兽听杨威利的舰队调动指令。
在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。
作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。
最终的决战已经展开，银河的历史又翻过了一页……
【输入文件】
输入文件galaxy.in的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。
以下有T行，每行有一条指令。指令有两种格式：
- M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。
- C i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。
【输出文件】
输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理：
如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。
【样例输入】
4
M 2 3
C 1 2
M 2 4
C 4 2
【样例输出】
-1
1
【样例说明】
战舰位置图：表格中阿拉伯数字表示战舰编号
| 第一列 | 第二列 | 第三列 | 第四列 | …… | |
| 初始时 | 1 | 2 | 3 | 4 | …… |
| M 2 3 | 1 | 3
2 |
4 | …… | |
| C 1 2 | 1号战舰与2号战舰不在同一列，因此输出-1 | ||||
| M 2 4 | 1 | 4
3 2 |
…… | ||
| C 4 2 | 4号战舰与2号战舰之间仅布置了一艘战舰，编号为3，输出1 | ||||
Previous Entries
Categories
Tag Cloud
Blog RSS
Comments RSS
Last 50 Posts
Back
Void 
Life 
Earth 
Wind 
Water 
Fire