FIFA Online 2

CB评估报告

2008-02-14

1 / 9

目 录

前言 .................................................................................................................................................. 3

一、FO2 CB网络架构 ...................................................................................................................... 4

1.1 每个站点的架构 ................................................................................................................ 4

1.2 PatchServer 架构 ............................................................................................................... 4

1.3 DownLoadServer架构 ........................................................................................................ 4

二、设备需求 ................................................................................................................................... 5

2.1 设备数量需求 .................................................................................................................... 5

A.) PatchServer ........................................................................................................... 5

B.) 电信站点 .................................................................................................................... 5

C.) 网通站点 .................................................................................................................... 6

D.) 合计 ............................................................................................................................ 6

2.2 设备采购............................................................................................................................ 6

A.) 交换机 ........................................................................................................................ 7

B.) 服务器 ........................................................................................................................ 8

C.) 磁盘阵列 .................................................................................................................... 8

三、带宽需求 ................................................................................................................................... 9

3.1 下载带宽............................................................................................................................ 9

3.2 游戏带宽............................................................................................................................ 9

A.) PatchServer .................................................................................................................. 9

B.) 电信区 ........................................................................................................................ 9

C.) 网通区 ........................................................................................................................ 9

2 / 9

前言

CB结束后可能平滑过度到OB阶段. 为此需要以OB的架构和需求进行准备. CB期间最高同时在线人数5000人。OB期间最高同时在线人数130000人. 站点方案：电信、网通各一个站点。人数比例分布为3.3:6.7 ．

3 / 9

一、FO2 CB网络架构

1.1 每个站点的架构

考虑到CB可能平滑过渡到OB,为了避免硬件防火墙瓶颈问题,建议游戏Server采用以下架构,对外采用三层交换机,在三层交换机之间采用堆叠模块进行连接,并在三层交换机上做端口策略.

盘阵

1.2 PatchServer 架构

由于patchserver可共用,因此建议将patchserver放置于与FO2站点完全独立的IDC中.当client更新档过大,则提供launcher更新和补丁更新2种方式.补丁更新档放置与DownLoadServer上. 采用LVS+iptables架构.

1.3 DownLoadServer架构

下载服务器用于提供给玩家下载FO2客户端及手动更新档.采用LVS+Iptables架构,主从LVS各一台.

4 / 9

二、设备需求

考虑CB可能平滑过度到OB,架构不在调整.

2.1 设备数量需求 A.) PatchServer

独立IDC,LVS架构(服务器5台，机柜1个).

B.) 电信站点

5 / 9

C.) 网通站点

网通站点的服务器承载人数3300人，设备需求如下: (服务器19台,盘阵1台,交换机2台，

D.) 合计

服务器数量: 47台

交换机数量: 4台 外网交换机: 2台 内网交换机: 2台 盘阵数量: 2台 机柜: 5个

2.2 设备采购

目前可用设备有: 服务器65台, 交换机3台。

尚需采购的设备数量：DB服务器2台（延用技术测试中DB所使用的DELL1950型号即可），外网交换机2台，盘阵2台。

6 / 9

服务器硬件需求如下：

A.) 交换机

内网交换机延用当前正在用的H3C SI-5100即可，不需要再采购。

外网交换机选用三层交换机（带堆叠模块），需要采购2台。

参考<< Fifa-CB外网交换机选型建议.doc >>

7 / 9

B.) 服务器

需要采购DB服务器2台（延用技术测试中DB所使用的DELL1950型号即可）

C.) 磁盘阵列

CB期间为了保险起见，建议采购盘阵，考虑到CB平滑过渡到OB，则所购阵列需要满足OB需求。

技术测试期间相关数据：25日电信最高在线3931，25日电信平均在线人数1293，时长30天，DB空间消耗增长约50M

每人平均每天使用50M/*1293人=40KB

OB后电信以每天最高在线87100人计算，平均在线人数约为87100*（1293 / 3931）=约30000人，则DB每天需要使用约30000人*40KB=1.2G磁盘空间，（存储上存放前一周每天的完整备份数据，备份数据压缩比率1/4），一年DB使用1.2G*365天=438G，备份数据约（438G/4）*7天=766.5G，则一年存储需要使用空间438G+766.5G=1205G，约1.2T；2年DB使用1.2G*365天*2年=876G，备份数据约（876G/4）*7天=1533G，则2年存储需要使用空间约876G+1533G=2409G，约2.5T。

主从DB共用一个阵列，每个DB使用一半数量的磁盘，阵列使用Raid5，以阵列存放2年的数据计算，则阵列最大存储容量需要至少2.5T*2=5T。每块磁盘的容量至少需要

2.5T/5=500G。

8 / 9

三、带宽需求

3.1 下载带宽

计算依据：总人次150000,前一周完成50%,平均每天完成约11000人,下载速率30k/s,客户端大小为1.2Gbyte,单位转换（1byte=10bit）,比率（实际带宽与满载带宽的比，以1.5计） 公式：

每天完成人数*（（客户端大小*单位转换系数）* 比率）/（每天的总秒数）=需求带宽 11000人*（（1.2Gbyte*10）*1.5）/（24*60*60）=2.3Gbps

3.2 游戏带宽

A.) PatchServer

计算依据：平均在线人数5000人计算,以每个玩家30Kb的下载速率.

每个区游戏带宽约为：5000*30Kb/S=150000Kb，即至少需要150Mb的游戏带宽 推荐游戏带宽：至少150Mb

B.) 电信区

计算依据：电信区峰值人数6700，每个玩家与GameServer之间需要6KByte/S的带宽。 每个区游戏带宽约为：6700*6KB/S = 40200 KB，即至少需要41MB的游戏带宽。 推荐游戏带宽：至少41 MB

C.) 网通区

计算依据：网通区峰值人数3300，每个玩家与GameServer之间需要6KByte/S的带宽。 每个区游戏带宽约为：3300*6KB/S = 19800 KB，即至少需要20MB的游戏带宽 推荐游戏带宽：至少20 MB

9 / 9

 

第二篇：树形DP

树形DP总结

顾名思义，树形DP就是在树上所做的动态规划。我们一般所做的动态规划多是线性的，线性DP我们可以从前向后或从后向前两种方法，不妨类比一下，在树上我们同样可以有两种方法，从根向树叶或者从树叶向根。从根向树叶的题不多见（至今我没见到过），而从根向叶传送值的题较多，下面我们主要来分析这种题。

在分析树形DP之前，我们要先会实现几个必要的程序，因为他们是我们完成一道题的前提，对于一道题，想法固然非常重要，想清楚写代码的时候就好写，但是如果我们无法实现一些基本的程序，比如如果不会将一棵多叉树改成一棵二叉树，那我们的程序就会复杂很多。不会搜索那么程序根本无法实现，所以说必须要弄清楚这些基本知识。

多叉树转换二叉树：

将一棵多叉树转换成二叉树，我们遵循的原则是：左儿子，右兄弟。

这句话的意思是，将一个点的儿子节点变成他的左子树的节点，他的左儿子，左孙子等。 而将他的兄弟节点变成他的右儿子，右孙子等。具体实现较为容易，读入一条从x到y的边，则用d数组记录x的最后一个儿子的编号，如果d[x]=0 则证明他还没有儿子节点，则将y点设为x点的左儿子，否则证明x点已经有了儿子节点，则把y记录成d[x]点的右儿子即可，这样就将一棵多叉树转换成了一棵二叉树，它的好处我们将会在下面对题目分析时提到。 参考代码：

Readln(x,y);

If d[x]=0 Then l[x]:=i Else r[d[x]]:=i;

d[x]:=i;

下面我们不妨分析几道题，摸索其中的一些解题的相同想法，得出一些经验。 例题分析：

提到树形DP，题的描述最符合的一道题应该是选课这道题。题目描述如下：

1.选课：

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

分析：

题意很明显的给出了一棵树，每个节点有一个权值，如果要取一个节点，那么必须取他的父节点，现在要在有限的课数的情况下修到最多的学分。根据题意描述，本题很直接的想到了要用到树形DP，我们不妨用F[I,J]表示选到第I门课，第I门课共选J门课时可取得的最大学分。现在要将j门课分到左右两棵子树上。

那么f[i,j]即为Max(f[l[i],k]+f[r[i],k]) +w[i](k=1...y)和f[r[i],j]的较大值。

我们将0当作根节点，-1当作空节点。

最后输出f[0,m]即为所求。

参考程序：

Program Ex;

Const

Infile='Ex.in';

Outfile='Ex.out';

Var

l,r,w,d:Array[-1..100] Of Longint;

f:Array[-1..100,-1..100] Of Longint;

n,m,i,j,x,y,ans:Longint;

Function Work(x,y:Longint):Longint;

Var

Max,k:Longint;

Begin

If (x<0) Then Exit(0);

Max:=0;

If f[r[x],y]=-1 Then f[r[x],y]:=Work(r[x],y);

Max:=f[r[x],y];

For k:=1 To y Do Begin

If f[l[x],k-1]=-1 Then f[l[x],k-1]:=Work(l[x],k-1);

If f[r[x],y-k]=-1 Then f[r[x],y-k]:=Work(r[x],y-k);

If f[l[x],k-1]+f[r[x],y-k]+w[x]>Max Then Max:=f[l[x],k-1]+f[r[x],y-k]+w[x]; End;

f[x,y]:=Max;

Exit(f[x,y]);

End;

Begin

Assign(Input,Infile);

Reset(Input);

Assign(Output,Outfile);

Rewrite(Output);

Readln(n,m);

For i:=1 To n Do Begin

l[i]:=-1;

r[i]:=-1;

w[i]:=-1;

End;

For i:=1 To n Do Begin

Readln(x,y);

w[i]:=y;

If d[x]=0 Then l[x]:=i Else r[d[x]]:=i;

d[x]:=i;

End;

For i:=-1 To n Do

For j:=-1 To n Do f[i,j]:=-1;

Ans:=Work(l[0],m);

Writeln(Ans);

Close(Input);

Close(Output);

End.

2.看守皇宫

问题描述：太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。

皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。

编程任务：帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。 分析：题目还是给出了一棵树，每个节点上有一个权值，表示在此点设置守卫所需要的花费。每个节点根据题目要求必须满足这三个条件之一：

（1）该节点设置了守卫

（2）该节点的父节点设置了守卫

（3）该节点的孩子节点设置了守卫

现在要求当所有节点均满足条件时所需的最小花费。

该题明显还是一道树形DP，刚做此题时我想的是一个二位F[I,J]的情况，I表示当前节点，J为0/1 0表示该节点不放置，1表示放置，但是若按此种方法想下去根本不对，因为无法保证价值最小。仔细想清楚，要在多加一维k表示当前节点他的祖先是否看守到他。这样就可以分成三个情景了。F[I,J,K]表示I节点 ，J为0/1 0表示该节点不放置，1表示放置 K为0/1 0表示该节点还未被看守，1表示该节点被看守。

(1) j=0 k=1

此种情况下，i节点已经保证被看守，他的孩子节点放或不放均可，但是孩子节点均未被祖先看守，则f[i,j,k]:=∑（x为i的孩子）Min(f[x,1,0],f[x,0,0]);

(2)j=0 k=0

此种情况下，i节点要想被看守，必须有他的孩子节点来看守，那么我们该怎么办呢？我们要是想要保证花费最少，则要找到f[x,1,0]-f[x,0,0]的最小值（x为i的孩子），这时我们将x点设置守卫，则可保证价值最少。

(3)j=1 k=0/1

这种情况就简单了，i节点有被看守，他的孩子可放可不放，孩子节点均被看守。 则f[i,j,k]:=∑（x为i的孩子）Min(f[x,1,0],f[x,0,0])+w[i];

这样输出f[root,0,0]和f[root,1,0] 的较小值就可以。

参考代码：

Program guard;

Const

Infile='';

Outfile='';

Var

Root,x,i,j,n,Ans,k:Longint;

Father,Num,w:Array[0..1500] Of Integer;

Child:Array[0..1500,0..1500] Of Integer;

F:Array[0..1500,0..1,0..1] Of Longint; //0 bu bei kan; 1 bei kan

Function Min(a,b:Longint):Longint;

Begin

If a<b Then Min:=a Else Min:=b;

End;

Function Work(x,y,z:Longint):Longint; //y wei dang qian jie dian kan bu kan

Var

i,Minn,k:Longint;

flag:Boolean;

Begin

Work:=0;

If (y=0) Then Begin

If (z=1) Then For i:=1 To Num[x] Do Begin

If f[Child[x,i],0,0]=-1 Then f[Child[x,i],0,0]:=Work(Child[x,i],0,0); If f[child[x,i],1,0]=-1 Then f[child[x,i],1,0]:=Work(child[x,i],1,0); Work:=Work+Min(f[child[x,i],0,0],f[child[x,i],1,0]);

End Else Begin

Flag:=False;

Minn:=Maxlongint;

For i:=1 To Num[x] Do Begin

If f[child[x,i],0,0]=-1 Then f[child[x,i],0,0]:=Work(child[x,i],0,0); If f[child[x,i],1,0]=-1 Then f[child[x,i],1,0]:=Work(child[x,i],1,0); k:=Min(f[child[x,i],0,0],f[child[x,i],1,0]);

If f[child[x,i],1,0]-f[child[x,i],0,0]<Minn Minn:=f[child[x,i],1,0]-f[child[x,i],0,0];

IF k=f[child[x,i],1,0] Then Flag:=True;

Work:=Work+k;

End;

If Not Flag Then Work:=Work+Minn;

End;

End;

If (y=1) Then Begin

Work:=Work+w[x];

For i:=1 To Num[x] Do Begin

If f[child[x,i],0,1]=-1 Then f[Child[x,i],0,1]:=Work(child[x,i],0,1); If f[child[x,i],1,1]=-1 Then f[child[x,i],1,1]:=Work(child[x,i],1,1); Work:=Work+Min(f[child[x,i],0,1],f[child[x,i],1,1]);

End;

End;

End;

Begin

Assign(Input,Infile);

Assign(Output,Outfile);

Reset(Input);

Rewrite(Output);

Readln(n);

For i:=1 To n Do Begin

Read(x);

Read(w[x]);

Read(Num[x]); Then

For j:=1 To Num[x] Do Begin

Read(Child[x,j]);

Father[Child[x,j]]:=x;

End;

Readln;

End;

For i:=1 To n Do If Father[i]=0 Then Begin

Root:=i;

Break;

End;

For i:=1 To n Do

For j:=0 To 1 Do

For k:=0 To 1 Do f[i,j,k]:=-1;

Ans:=Min(Work(Root,0,0),Work(Root,1,0));

Writeln(Ans);

Close(Input);

Close(Output);

End.

3.sgu134

You are given an undirected connected graph, with N vertices and N-1 edges (a tree). You must find the centroid(s) of the tree.

In order to define the centroid, some integer value will be assosciated to every vertex. Let's consider the vertex k. If we remove the vertex k from the tree (along with its adjacent edges), the remaining graph will have only N-1 vertices and may be composed of more than one connected components. Each of these components is (obviously) a tree. The value associated to vertex k is the largest number of vertices contained by some connected component in the remaining graph, after the removal of vertex k. All the vertices for which the associated value is minimum are considered centroids.

题意为给定一棵树，求一棵树的重心，一棵树的重心定义为：去掉某一个节点后出现一个森林，这个森林里的树的节点最多的值为此点权值，权值最大的点为这棵树的重心。 那么现在我们要求的就是每个点的权值，每个点的权值为这两个值的较大值：

（1）他的子树的点的数目的最大值

（2）点的总数除去以这个点为跟的树的点的数目

子树的点的数目怎么求呢？深搜可以解决。

这样就求出了每个点的权值。

参考代码：

Program sgu134;

Const

Infile='';

Outfile='';

Var

num,i,n,ans,ansn,x,y:Longint;

maxx,numm,a,b,next,fa,dp:Array[0..100000] Of Longint;

Function Max(a,b:Longint):Longint;

Begin

If a>b Then max:=a Else max:=b;

end;

Procedure Addedge(x,y:Longint);

Begin

Inc(num);

a[num]:=y;

next[num]:=b[x];

b[x]:=num;

End;

Procedure Dfs(x:Longint);

Var

i,v:Longint;

Begin

Numm[x]:=1;

Maxx[x]:=0;

i:=b[x];

While i>0 Do Begin

v:=a[i];

If Numm[v]=0 Then Begin

fa[v]:=x;

Dfs(v);

numm[x]:=numm[x]+numm[v];

If numm[v]>Maxx[x] Then Maxx[x]:=numm[v]; End;

i:=Next[i];

End;

End;

Begin

Assign(Input,Infile);

Assign(Output,Outfile);

Reset(Input);

Rewrite(Output);

Readln(n);

For i:=1 To n-1 Do Begin

Readln(x,y);

Addedge(x,y);

Addedge(y,x);

End;

Dfs(1);

ans:=Maxlongint;

For i:=1 To n Do Begin

dp[i]:=Max(Maxx[i],n-numm[i]);

If dp[i]<ans Then Begin

Ans:=dp[i];

ansn:=1;

End Else If (dp[i]=ans) Then Inc(ansn);

End;

Writeln(ans,' ',ansn);

For i:=1 To n Do If dp[i]=ans then Write(i,' ');

Writeln;

Close(Input);

Close(Output);

End.

4.sgu149

A school bought the first computer some time ago. During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know for each computer number Si - maximum distance, for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.

分析：题意为给定一棵树，给出边的权值，求树中每个点到其他所有点中距离的最大值。此题可以想一个顶点到其他点距离最大值，此点可能在他的子树里，也可能在他的子树外，刚开始我想的是只用两个数组分别记录他到子树的最大值和他到外面的最大值即可。可是后来发现一个节点x到外边的最大值是他的父节点father[x]到外边的最大值，到子树的最大值，但是有可能x在father[x]取子树的最大值的子树上，所以要想到一些改变，除了记录子树的最大值，还要记录子树的次大值，这样一个点到他的子树的最大值，次大值可以由深搜得到，到外面的最大值分三种情况：

（1）dist[x]=cost[x]+dist[father[x]];

（2）Dist[x]=cost[x]+deep1[father[x]] x不在最大子树上

（3）Dist[x]=cost[x]+deep2[father[x]] x在最大子树上

这样输出dist[x] 和deep1[x] 的最大值即可

参考代码：

Program sgu149;

Const

Infile='';

Outfile='';

Var

father,cost,a,c,next,b,deep1,deep2,dist:Array[0..10050] Of Longint;

i,n,x,w,num:Longint;

Procedure Addedge(x,y,w:Longint);

Begin

Inc(num);

a[num]:=y;

c[num]:=w;

Next[num]:=b[x];

b[x]:=Num;

father[y]:=x;

Cost[y]:=w;

End;

Procedure Dfs(x:Longint);

Var

i,v:Longint;

Begin

deep1[x]:=0;

deep2[x]:=0;

i:=b[x];

While (i>0) Do Begin

v:=a[i];

Dfs(v);

If deep1[v]+c[i]>deep1[x] Then Begin

deep2[x]:=deep1[x];

deep1[x]:=deep1[v]+c[i];

End Else If deep1[v]+c[i]>deep2[x] Then

deep2[x]:=deep1[v]+c[i];

i:=Next[i];

End;

End;

Procedure Work(x:Longint);

Var

i:Longint;

Begin

Dist[x]:=Dist[father[x]];

If Deep1[x]+Cost[x]=Deep1[father[x]] Then Begin

If deep2[father[x]]>dist[x] Then dist[x]:=deep2[father[x]]; End Else Begin

If deep1[father[x]]>dist[x] Then dist[x]:=deep1[father[x]]; End;

dist[x]:=dist[x]+cost[x];

i:=b[x];

While i>0 Do Begin

Work(a[i]);

i:=Next[i];

End;

End;

Begin

Assign(Input,Infile);

Assign(Output,Outfile);

Reset(Input);

Rewrite(Output);

Readln(n);

For i:=2 To n Do Begin

Readln(x,w);

Addedge(x,i,w);

End;

Dfs(1);

Work(1);

For i:=1 To n Do If deep1[i]>dist[i] Then Writeln(deep1[i])

Else Writeln(dist[i]);

Close(Input);

Close(Output);

End.

5.sgu195

All programmers of Mocrosoft software company are organized in a strict subordination hierarchy. Every programmer has exactly one chief, except Bill Hates who is also the head of the company and has no chief.

Due to the celebration of the new 2003 year, chief accountant of Mocrosoft decided to pay a New Year Bonus Grant of 1000 dollars to some programmers. However being extremely concerned of the company wealth she would like to designate the least possible amount of money for these grants. On the other hand she didn't want to be accused of being too greedy or of giving preferences to some programmers. To do this, she developed the following scheme of grants appointment:

Each programmer may either assign a grant to one of his subordinates or have a grant assigned to him by his chief or none of the above.

No programmer can simultaneously receive a grant and assign a grant to one of his subordinates.

No programmer can assign a grant to more than one of his subordinates

The scheme seemed to be designed perfectly — nobody would like to assign a grant to anybody since in this case he himself would not receive money. But programmers somehow discovered the plan of chief accountant and decided to make a trick to get the most money possible and share them fairly afterwards. The idea was to make such grant assignments that the total amount of grant money received is maximum possible.

You were selected to write the program which will find the optimal grants appointment.

分析：本题求的是最多能给多少个人发奖金，能给一个人发奖金要满足2个条件：

（1）不是根节点

（2）一个点和他的儿子节点中只能选一个

现在我们不妨用0表示取此点，1表示不取 则

f[x,0]=∑(v 为x儿子节点）f[v,1]+1;

f[x,1]=∑（v为x儿子节点）f[v,1]+Max(f[v,0]-f[v,1]); 这样f[1,1] *1000 即为所求

参考代码：Program sgu195;

Const

Infile='';

Outfile='';

Var

Father,a,b,c,next,Ans:Array[0..2000000] Of Longint; f:Array[0..2000000,0..1] Of Longint;

i,n,num,Ansn:Longint;

Procedure Qsort(l,r:Longint);

Var

i,j,x,y:Longint;

Begin

i:=l;j:=r;x:=ans[(l+r) Div 2];

Repeat

While (ans[i]<x) Do Inc(i);

While (ans[j]>x) Do DeC(j);

If i<=j Then Begin

y:=ans[i];

ans[i]:=ans[j];

ans[j]:=y;

Inc(i);

Dec(j);

End;

Until i>j;

If i<r Then Qsort(i,r);

If l<j Then Qsort(l,j);

End;

Procedure Addedge(x,y:Longint);

Begin

Inc(num);

a[num]:=y;

Next[num]:=B[x];

B[x]:=num;

End;

Procedure Dfs(x:Longint);

Var

Ans,Max,i,v:Longint;

Begin

Ans:=0;

Max:=-Maxlongint;

f[x,0]:=1;

i:=B[x];

While (i>0) Do Begin

v:=a[i];

Dfs(v);

Ans:=Ans+f[v,1];

If (f[v,0]-f[v,1]>Max) Then Begin Max:=f[v,0]-f[v,1];

c[x]:=v;

End;

i:=Next[i];

End;

f[x,0]:=f[x,0]+Ans;

If f[x,1]<Max+Ans Then f[x,1]:=Max+Ans; End;

Procedure Work(x,y:Longint);

Var

i,v:Longint;

Begin

If y=0 Then Begin

Inc(Ansn);

Ans[ansn]:=x;

End;

i:=b[x];

While i>0 Do Begin

v:=a[i];

If y=0 Then Work(v,1) Else

If c[x]=v Then Work(v,0) Else Work(v,1); i:=Next[i];

End;

End;

Begin

Assign(Input,Infile);

Assign(Output,Outfile);

Reset(Input);

Rewrite(Output);

Readln(n);

For i:=2 To n Do Begin

Read(father[i]);

AddEdge(father[i],i);

End;

Dfs(1);

Writeln(f[1,1]*1000);

Work(1,1);

Qsort(1,Ansn);

For i:=1 To Ansn Do Write(ans[i],' ');

Writeln;

Close(Input);

Close(Output);

End.

6.九头龙

传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”，但这只是说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的总数会远大于九，当然也会有旧头因衰老而自己脱落。

有一天，有M个脑袋的九头龙看到一棵长有N个果子的果树，喜出望外，恨不得一口把它全部吃掉。可是必须照顾到每个头，因此它需要把N个果子分成M组，每组至少有一个果子，让每个头吃一组。

这M个脑袋中有一个最大，称为“大头”，是众头之首，它要吃掉恰好K个果子，而且K个果子中理所当然地应该包括唯一的一个最大的果子。果子由N-1根树枝连接起来，由于果树是一个整体，因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。

对于每段树枝，如果它所连接的两个果子需要由不同的头来吃掉，那么两个头会共同把树枝弄断而把果子分开；如果这两个果子是由同一个头来吃掉，那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。当然，吃树枝并不是很舒服的，因此每段树枝都有一个吃下去的“难受值”，而九头龙的难受值就是所有头吃掉的树枝的“难受值”之和。

九头龙希望它的“难受值”尽量小，你能帮它算算吗？

例如图1所示的例子中，果树包含8个果子，7段树枝，各段树枝的“难受值”标记在了树枝的旁边。九头龙有两个脑袋，大头需要吃掉4个果子，其中必须包含最大的果子。即N=8，M=2，K=4：

大头吃4个果子，用实心点标识；

小头吃4个果子，用空心点标识；

九头龙的难受值为4，因为图中用细边标

记的树枝被大头吃掉了。

图一 图二

图一描述了果树的形态，图二描述了最优策略。

分析：此题为一道较难的树形DP，他的难点在于大头必须要吃的果子是给出的。现在我们先把这颗树转换成二叉树，这样后边的处理要比不转化简单很多，之后进一步分析，我们其实并不惧怕头多的情况，毕竟如果头数>2,我们完全不用考虑吧小头的难受度，他们完全可以分层吃而保证没有难受值。但如果只有两个头，则还要考虑小头的难受度。这是我们来想肯定至少是一个三维的dp，一维记录当前节点，一维记录当前节点有几个果子等待分配，还有一维记录该点父节点是否被吃，这是判断是否要加上难受值用的。我们用一次深搜来将每个点的以自己为根节点的树的节点个数求出来，这个在后面枚举分配果子时要用到。然后就要开始dp了，f[x,y,z]表示x节点，z为0/1，0表示x

的父节点没吃，1表示吃了，y为x节点待分配果子数。现在要判断x点吃不吃. temp1表示x点不吃时左儿子取得值f[l[x],i,0] i=0..Min(sum[x],y);

如果m=2 z=0 则temp1=temp1+w[x]

temp2表示x 点吃时左儿子取得值f[l[x],i-1,1]i=0..Min(sum[x],y);

如果g=1 则temp2=temp2+w[x]

temp3 表示右儿子的情况 f[r[x],y-i,z]i=0..Min(sum[x],y);

那么f[x,y,z]=Min(f[x,y,z],Min(temp1,temp2)+temp3);

这样输出f[l[1],k-1,1]即可

参考代码：

Program dragon;

Const

Infile='dragon.in';

Outfile='dragon.out';

Var

n,m,k,i:Longint;

Sum,l,r,w:Array[0..500] Of Longint;

f:Array[-1..500,-1..500,-1..1] Of Longint;

Function Dp(Root,Num,g:Longint):Longint;

Var

temp1,temp2,temp3,i:Longint;

Begin

temp1:=0;

temp2:=0;

temp3:=0;

If (root=0)And(num=0)Then Exit(0);

If (num<0) Then Exit(100000000);

If (f[root,num,g]>=0) Then Exit(f[root,num,g]);

f[root,num,g]:=100000000;

For i:=0 To Min(num,Sum[Root]) Do Begin

temp1:=dp(l[root],i,0);

If (m=2)And(g=0) Then temp1:=temp1+w[root];

temp2:=dp(l[root],i-1,1);

If (g=1) Then temp2:=temp2+w[root];

temp3:=dp(r[root],num-i,g);

temp1:=Min(temp1,temp2);

f[root,num,g]:=Min(f[root,num,g],temp1+temp3);

End;

Exit(f[root,num,g]);

End;

Procedure Work;

Var

Ans,i,j,z:Longint;

Begin

If n-k<m-1 Then Begin

Writeln('-1');

Exit;

End;

Fillchar(f,Sizeof(f),255);

Writeln(Dp(l[1],k-1,1));

End;

Begin

Assign(Input,Infile);

Assign(Output,Outfile);

Reset(Input);

Rewrite(Output);

Init;

Work;

Close(Input);

Close(Output);

End.

总结：上面我们一共分析了6道例题，可以发现其中有很多想法是一样的，比如记录父节点是否访问，比如用深搜求一些和子树有关的信息，这些应该在以后面对新题的时候灵活选择应用，才能掌握好树形dp。树形dp也是dp，思路想法还是有相同之处的，想清楚的话还是可以实现一些题目的。