对一类动态规划问题的研究
湖南省长沙市第一中学徐源盛
【关键字】
动态规划费用提前计算假设未来决策
【摘要】
本文通过四道题目探讨了一种比较特殊的动态规划问题，即当前决策影响未
来“行动”的费用。如果当前决策对未来的影响只与当前决策有关，则直接将对
未来费用的影响，算作当前的决策费用计算，并通过状态传递；如果对未来的影
响还与未来的情况有关，则新增状态假设未来的情况，待到未来决策时直接使用
假设的状态。这就是本论文详细阐述的解题方法。
【正文】
在常规动态规划问题中，我们面临当前状态时“行动”造成的花费往往与这个
状态是同时计算的。例如在经典的石子合并问题中，规划方程为
f[i][j]=max{f[i][k]+f[k+1][j]}+w(i,j)，当我们计算f[i][j]时，才会把将i到j的石子全部
合并到一起这一“行动”的费用加进去。这很符合我们的思维习惯。
然而近年来频繁出现一类动态规划问题，在这类问题中，当前“行动”的费用
的一部分需要在之前决策时被计算并以状态的形式对当前状态造成影响。造成这
一独特的计算的原因就是当前的决策会对未来的“行动”费用造成影响。这类问题
构造方程往往比较困难，需要仔细分析原题，找到矛盾所在。
一、当前决策对未来“行动”的费用影响只与当前决策有关
比如在两男两女中选一男一女去执行任务，已知每个人的效率，希望总效率
最高。并且男A如果被选，所有女生的效率加7，如果男B被选，所有女生的效
率减7。在第一阶段选男A还是男B对第二阶段女生的效率有不同的影响，可以
将对女生的影响当做男生的“自身魅力”，即把男A的效率加7，男B的效率减
7。而我们实际上是把第二阶段的费用在第一阶段计算了。对于这类问题我们往
往将对未来“行动”的影响一并算做当前决策的费用。下面通过两道例题进行详细
阐述。
【问题一】Sue的小球(sdtsc2008)
Sue和Sandy最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且
充满刺激的大海上。Sue有一支轻便小巧的小船，然而，Sue的目标并不是当一
个海盗，而是要收集空中漂浮的彩蛋。Sue有一个秘密武器，只要她将小船划到
一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩
蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Sue要想得
到更多的分数，必须尽量在魅力值高的时候收集这个彩蛋，而如果一个彩蛋掉入
海中，它的魅力值将会变成一个负数，但这并不影响Sue的兴趣，因为每一个彩
蛋都是不同的，Sue希望收集到所有的彩蛋。
Sandy就没有Sue那么浪漫了，Sandy希望得到尽可能多的分数，为了解决
这个问题，他先将这个游戏抽象成了如下模型：
以Sue的初始位置所在水平面作为x轴。
一开始空中有N个彩蛋，对于第i个彩蛋，他的初始位置用整数坐标（xi,yi）
表示，游戏开始后，它匀速沿y轴负方向下落,速度为vi单位距离/单位时间。Sue
的初始位置为(x0,0)，Sue可以沿x轴的正方向或负方向移动，Sue的移动速度是
1单位距离/单位时间，使用秘密武器得到一个彩蛋是瞬间的，得分为当前彩蛋
的y坐标的千分之一。
现在，Sue和Sandy请你来帮忙，为了满足Sue和Sandy各自的目标，你决
定在收集到所有彩蛋的基础上，得到的分数最高。
输入文件
第一行为两个整数N,x0用一个空格分隔，表示彩蛋个数与Sue的初始位置。
第二行为N个整数xi，每两个数用一个空格分隔，第i个数表示第i个彩蛋
的初始横坐标。
第三行为N个整数yi，每两个数用一个空格分隔，第i个数表示第i个彩蛋
的初始纵坐标。
第四行为N个整数vi，每两个数用一个空格分隔，第i个数表示第i个彩蛋
匀速沿y轴负方向下落的的速度。
输出文件
一个实数，保留三位小数，为收集所有彩蛋的基础上，可以得到最高的分数。
样例
输入样例(ball.in的内容)：
30
-4-22
223026
198
输出样例(ball.out的内容)：
0.000
数据范围
N<=20，对于30%的数据。
N<=1000，对于100%的数据。
-104<=xi,yi,vi<=104，对于100%的数据。
【分析】
先把所有的点包括起点按x值排序，这样题目就变成从起点出发，每次可以
向左或向右走到最近的某个彩蛋，将其射落，设每个彩蛋第一次走到的时刻为ti，
答案就是∑(yi-tivi)，使答案最大。
我们注意到已射落的彩蛋集合是不断增大的，这样很容易想到用f1[i][j]、
f2[i][j]分别表示从起点出发已射落i到j这一段彩蛋，当前停留在i点、j点的最
大得分。考虑f1[i][j],即点i是当前射击的彩蛋，射击的得分与当前时刻挂钩，但
是当前的时刻是不能从f1[i][j]的状态中表示出来的。如果我们再添一维状态表示
时间，这样时间复杂度是不允许的。
我们发现上述方法的矛盾其实就在于曾经的行走方案会对当前射击的得分
产生影响，我们可以进一步考虑f1[i][j]的求解，由于射击i的得分是yi-tvi，而t
等于之前每一步决策移动的时间总和，这样我们就可以像前述的男生女生问题一
样，把-tvi在之前的移动中就计算，也就是说每次移动都要把未来会减少的得分
计算在内。比如说从f1[i][j]推到f1[i-1][j]，即从i走到i-1时除了i到j这一段彩蛋
外，其它的彩蛋都在下落，将这丢失的分数一并计算到从i走到i-1中。由于-tvi
已经在之前决策时计算，所以射击时加上yi即可。
为了方便描述，用w[i][j]表示∑(v)-?
?
j
ikkv][
，即除了i到j这一段的彩蛋外的
所有彩蛋下落速度和，那么很容易得到方程：
f1[i][j]=y[i]+max{f1[i+1][j]-(xi+1-xi)w[i+1][j],
f2[i+1][j]-(xj-xi)w[i+1][j]}
f2[i][j]=y[j]+max{f2[i][j-1]-(xj-xj-1)w[i][j-1],
f1[i][j-1]-(xj-xi)w[i][j-1]}
答案就是max(f1[1][n]，f2[1][n])/1000。算法的时间复杂度为O(n2)。至此问
题已得到完全解决。
回顾上述解题过程，我们发现射击彩蛋的得分被分成两部分计算了，而全体
彩蛋下降只与当前移动的时间有关，这使得我们可以把未来的得分一并计算到当
前状态中。
【问题二】名次排序问题(BOI2007day1)
已知参赛选手的得分，你的任务是按照得分从高到底给出选手的排名。遗憾
的是，保存选手信息的数据结构只支持一种操作，即将一个选手从位置i移动到
位置j，该移动不改变其他选手的相对位置，即如果i>j，位置j和位置i-1之间的选
手的位置都比原来加1，相反如果i
原来减一。上述移动的操作的代价定义为i+j，这里，位置编号从1开始。
请你编程确定一个移动选手的步骤，将选手按照得分从高到低排序，并使整
个移动过程的总代价最小。
输入：
文件sorting.in第一行为一个整数n（2<=n<=1000），表示选手的人数；接下来
的n行，每行一个非负整数Si(0<=Si<=1000000)，表示一个选手的得分。你可以认
为每人的得分是不同的。
输出：
文件sorting.out的第一行为一个整数，表示移动的次数，接下来的每一行表
示一个移动步骤，每个移动步骤用两个整数i,j表示，表示位置i的选手移动到位
置j，i和j之间有一个空格隔开。
样例
soring.insorting.out
5
20
30
5
15
10
2
21
35
【分析】
为了方便讨论，将每个点的值修改为其目标位置，这样目标状态就是1到n。
假设n+1号人在n+1位置。初看此题感到无从下手，稍加分析，不难发现：将i
移动到j位置有两种方法，即主动移动与被动移动，而且我们感觉上觉得一个人
如果移动多次不如一步到位。
[猜想2.1]一个人最多移动一次，如果移动则必然移动到编号比他大1的人
前面。
因为往后移动会使部分人的位置减1，从而减少此人未来的移动费用，所以
编号越大的越先移动。
[猜想2.2]按编号从大到小进行移动。
由于上述猜想的证明不是本论文的重点，在此省略，详细证明在附录中。
[结论2.1]：按编号从大到小进行操作，对于每个人x有两种选择:
1.移动到x+1前一个位置。
2.如果x在x+1前，则不移动，以后再将所有处于x和x+1之
间的移动到x之前。
考虑将处于位置i的x向后移动到处于j(j>i)的x+1前。由[结论2.1]我们可知，
当前小于x+1的都没有移动，也就是说所有小于等于x的数的相对位置与最初的
一样[推论2.1]。又因为比x+1大的数要么在之前移动了，要么x+1移动到它前面
了，所以所有比x+1大的数都位于x+1后面[推论2.2]。注意到这一题移动会导
致位置的改变，i和j已经不再是最初x和x+1所在的位置了。那我们该怎么办呢？
前面提到了相对位置是不会变的，可否在此做文章？
如图2.1，把5放到4后面，得到如图2.2所示。1和4都向前移动一位，
如果我们修改规则，让5和4共用位置5得到图2.3，从而并没有移动1和4，
而此时1、2、3、4的相对位置仍然没改变。其实我们可以利用相对位置求出绝
对位置！如果x的原位置为p1，由[推论2.1]和[推论2.2]可知x的实际位置为最
开始1到p1中比x小的数的个数加1（加上自己）。但是x+1可能移动了，那么
在原序列中的位置只能枚举，设为p2。用c(p,x)表示处理完x+1到n后x在原序
列中位置p，那么x的实际位置为c(p,x)。c(p,x)等于原序列中从1到p有比x小
的数的个数加1，那么把x从原序列的p1移动到x+1所在的p2的费用为
c(p1,x)+c(p2,x+1)-1（因为是把x插入到x+1前，所以要减1）。
例如，在图2.4中，把3插入到4前面一位，由图2.5易知i=1,j=4。3的实
际位置为图2.4中在3前面且比3小的数的个数加1为1，同理4的实际位置为
4（5必然在4后面），这次移动的费用为1+4-1，的确与图2.5的实际情况相吻
合。为了不影响1、2的位置，3在移动后在原序列中位置变成了5，真实位置为
3，如图2.6所示，也就是说经过这次移动后3，4，5的原序列中位置均为5。
我们可以令f[x][p2]表示把x移动到原序列的p2位置且x+1到n都在p2的
最小费用。pos[x]表示x在原序列中位置。则对于向后移动的情况，有方程
f[x][p2]=f[x+1][p2]+c(pos[x],x)+c(p2,x+1)-1(p2>pos[x])。
接着我们考虑j
移动到4之前时，3的位置并不等于c(5,3)，而是c(5,3)+2；如果当初5的决策是
移动到最后，而4的决策是不移动，如图2.8，也就是4在原序列中位置仍为2，
这样把3移动到4之前时，3的位置是c(5,3)+1。也就是说过去的决策对当前3
的移动费用造成了影响。不妨仿造问题一的处理方法，将对未来的影响一并计算
到当前状态，这样ji的情况。
下面我们考虑如何计算对未来状态的影响。
如果x不移动，则x+1必然在x后面的某个位置，设在原序列中位置分别为
p1,p2，p1=pos[x]。还是考虑图2.7，当我们决定5不移动时，如果4移动到5的
前面，或者4不移动，3都要跨越4和5。也就是说3在未来移动时位置为
3521431245
图2.4图2.55
35214
图2.65
3
35214
图2.1
31245
图2.2
35214，5
图2.3
1245312453
图2.7图2.85
c(5,3)+(5-3)，而c(5,3)这部分费用会在将来的移动中被计算，当前需要增加的仅
有(5-3)。总而言之，如果我决定x不移动，虽然这一步并不产生费用，但是要将
未来的一部分必然会产生的费用计算，那就是所有位置大于pos[x]小于p2的比
x小的数与x差的和。用方程表示：
f[x][pos[x]]=min{f[x+1][p2]+??
????
12
1][][])[(
p
xposkksxksx
}p2>pos[x]
综上所述，此题的方程为：
f[i][j]=f[i+1][j]+c(pos[i],i)+1+c(j,i)+1
f[i][pos[i]]=min{f[i][pos[i]],f[i+1][j]+??
????
1
1][][])[(
j
iposkksiksi
}j>pos[i]}
答案就是min{f[1][i]}1<=i<=n。时间复杂度O(n2)。
【小结】
回顾第一题的解题历程，我们先发现当前“行动”的费用受到过去决策的影
响，如果新增状态t表示过去决策的影响，状态数过大将会无法承受，于是我们
将受到的影响在过去决策时计算，通过状态传递过来。
我们之所以能这样做是有条件的：
一、影响是必然的。在问题一中，只要我们一移动，彩蛋就会下降。在问题
二中，只要我决定不移动，未来的费用就会增加一个固定值。如果问题一不要求
射击所有彩球，那么未来不会被射击到的彩球就不会被影响，因而就不能使用上
述方法解决。
二、影响是关于当前决策的函数。问题一中的函数是-t∑v，∑v与状态有关，
可以看成常数，-t即当前决策的移动时间。问题二的函数同样满足。
以上两个条件综合来讲就是当前决策对未来“行动”费用的影响只与当前决
策有关。
二、当前决策对未来“行动”的费用影响不只与当前决策有关
有些问题并非像上述问题这么简单，当前决策对未来“行动”费用的影响还有
可能与未来的情况有关。这时我们往往多开几维状态来假设未来的决策，从而像
之前那样将部分费用提前计算，待到未来决策时即可直接使用。
【问题三】方块消除(算法艺术与信息学竞赛)
Jimmy最近买了台电脑，很快，像大多数孩子一样，他迷上了游戏。最近，
他正在玩一款叫做方块消除的游戏。游戏规则如下：
如图，n个带颜色的方格排成一行。
相同颜色的方块就会连成一个区域（如果两个相邻方块颜色相同则这两个方
块属于同一区域）。你可以任选一个区域消去。设这个区域包含的方块数为x，
则你将得到x2的分值。方块消去之后，其右边的方块会往左移动，与左边的相
连。
【分析】
我们可以先把同色的合并，假设用(a,b)表示有b个a颜色的方块相连。
每次消除一个区域，加上这个区域的得分，这很像石子合并问题，很容易让
人尝试用f[i][j]表示把区域i到区域j的方块消除完的最大得分。考虑区域j，如
果单独消除，那么f[i][j]=f[i][j-1]+bj2。还有一种情况，区域j与之前的某些同色的
方块合并成新区域再消除。可是必须知道合并后的长度才能计算得分，但是仅从
当前的状态是无法得知的，如果我们新增状态假设过去的情况，那么我们要表示
过去的每一块方块是否消除，新增状态数多到无法承受。
假设我们还像前面两题那样的方法去解决，假设当前消去一个长3的红色方
块，过去留了一个长3的红色方块，总共消去得分是62=36，但是36并不能像
上面两题那样进行拆分计算，究其原因，这是一个二次函数，在过去留下长3
的红色方块时对我们现在一起消去的影响与我们现在消去的长度是有关的。
这时我们只能换个思路，先理清我们要做的：我们要把区域j与之前的某些
同色方块合并，如果这次合并在之前被料到了并预先计算了得分，并通过状态传
递到了现在，那我们不就能构造出一个动态规划方程了么？也就是说对于当前的
f[i][j]我们还要假设经过一些消除操作后，有k个与aj同色的方块连在了区域j后
形成新的长度为（bj+k）的区域，即用f[i][j][k]表示将i到j合并，并且假设未来
会有k个与aj同色的方块与j相连的最大得分。为什么只要记录j在未来会有多
少个与之相连，而不用记录i到j-1的呢？
[证明3.1]
如图3.1所示，如果区域j未来会与k2相连，也就是说j+1到k2-1之间的区
域需要先于区域j被消掉，所以区域j之前的区域必然不能与j到k2之间的区域
相连。如图3.2所示，如果j未来会与k1相连，j之前的某点i会与k2相连，那
么我们可以把消去i的得分在计算f[i][k2]时加进去。
于是我们得到[结论3.1]：对于状态f[i][j][k]，不论经过什么操作,区域i到区域j-1
之间的区域只能与区域i到区域j之间的区域相连，而区域j可以与j之后的区域
相连。
因此我们得到方程：
（1）如果直接消去第j个区域和未来会接到j后面的k块，那么
f[i][j][k]=f[i][j-1][0]+(bj+k)2。
（2）如果j与之前一起合并，假设与j颜色相同的是区域p，那么
f[i][j][k]=f[i][p][k+bj]+f[p+1][j-1][0]（i<=p
f[i][j][k]为两者的最大值。
答案即是f[1][n][0]。时间复杂度为O(n4)。本来我们想将计费摊在之前每一
I
J
K1
K2
图3.1
I
J
K1
K2
图3.2
次“保留，以后消除”的决策上，但是我们发现这些计费不是独立的，是相互关联
的，当前的费用还需知道未来的情况，所以我们可以再开一维状态，用以记录未
来的情况。
【问题四】奥运物流(NOI2008day2)
2008北京奥运会即将开幕，举国上下都在为这一盛事做好准备。为了高效
率、成功地举办奥运会，对物流系统进行规划是必不可少的。物流系统由若干物
流基站组成，以1…N进行编号。每个物流基站i都有且仅有一个后继基站Si，而
可以有多个前驱基站。基站i中需要继续运输的物资都将被运往后继基站Si，显
然一个物流基站的后继基站不能是其本身。编号为1的物流基站称为控制基站，
从任何物流基站都可将物资运往控制基站。注意控制基站也有后继基站，以便在
需要时进行物资的流通。在物流系统中，高可靠性与低成本是主要设计目。对于
基站i，我们定义其“可靠性”R(i)如下：设物流基站i有w个前驱基站P1,P2,P3…Pw
即这些基站以i为后继基站，则基
站i的可靠性R(i)满足下式：
R(i)=Ci+?
?
w
jj
PRk
1
)(
其中Ci和k都是常实数且恒为正，且有k小于1。整个系统的可靠性与控制基
站的可靠性正相关，我们的目标是通过修改物流系统，即更改某些基站的后继基
站，使得控制基站的可靠性R(1)尽量大。但由于经费限制，最多只能修改m个基
站的后继基站，并且，控制基站的后继基站不可被修改。因而我们所面临的问题
就是，如何修改不超过m个基站的后继，使得控制基站的可靠性R(1)最大化。
输入格式
输入文件trans.in第一行包含两个整数与一个实数，N,m,k。其中N表示基
站数目，m表示最多可修改的后继基站数目，k分别为可靠性定义中的常数。
第二行包含N个整数，分别是S1,S2…SN，即每一个基站的后继基站编号。
第三行包含N个正实数，分别是C1,C2…CN，为可靠性定义中的常数。
输出格式
输出文件trans.out仅包含一个实数，为可得到的最大R(1)。精确到小数点
两位。
输入样例
410.5
2313
10.010.010.010.0
输出样例
30.00
【分析】
将每个点向它的后继发出一条边，稍加分析不难得出，此题的图是一些树，
树的根节点连成一个环。
对于一棵以i为根的树，通过方程的迭代，我们发现R(i)等于所有以i为根的树
中包含的点x的可靠常数Cxkd(x,i)的和。d(x,i)表示x到i经过的边数。
考虑环，如图4.1，一个长度为3的环。R(1)=C1+kR(2)。R(2)=C2+kR(3)。
R(3)=C3+kR(1)。消元得R(1)=C1+kC2+k2C3+k3R(1)。R(1)=(C1+kC2+k2C3)/(1-k3)。即环上
每个点的x的可靠常数Cxkd(x,1)的和除以(1-klen)，Len表示环的长度。
如图4.2所示，每个点x对R(1)的贡献为Cxkd(x,i)kd(i,1)=Cxkd(x,1)。于是我们得到：
R(1)=??
?
n
j
idkci
1
)1,(/(1-klen)。我们枚举环的长度，即修改环上某个点的
后继，这样1-klen确定，只需分子尽可能大。现在我们有m次修改机会，因为环已
经确定，所以不能再修改树根的后继，只能改变一个非树根点的后继。根据公式，
显然每次修改都应该把修改点的后继直接设置为1。
尝试使用动态规划，如图4.3，我们很容易想到，用在以i为根的树中，修改
了j次的最大值来表示状态。对于点i我们有修改和不修改两种方式。
如果不修改i的后继，我们要把j次修改分配到i的子树中，然后加上i在当前状
态下对1的贡献Cikd(i,1)。
如果将i的后继修改为1，i为根的树对R(1)的贡献怎么计算呢？我们发现，假
如i的子孙都没修改过，将点i的后继设置成点1，那么点i及点i的子孙到点1的距离
都减少了2，即贡献值都除以k2。但是如果点2的后继在之前已经被设置成了1，
13
2
图4.1
1
i
X
图4.2
×k
×k
×k
×k
i
X
3
2
1
图4.3
Y
那当我们把点i的后继修改成点1的时候点2的距离并没有减少2。也就是说点2的
决策影响着改变点i后继的费用。难道我们新增状态表示树i中哪些点被修改过，
哪些点没被修改过？显然状态量是无法承受的。
我们需要把点2对修改点i时的费用贡献在决策点2的时候计算。即当我们决
策点2时，加上未来的费用贡献。可是我们应该增加多少呢？如果点i后继修改为
点1，点2的距离为2。如果点i没有修改而是点y修改到点1，点2的距离是3，点2
的贡献取决于离它最近的被修改的祖先，需要新增状态表示离它最近的被修改的
祖先。用f[i][j][d]表示以点i为根的树中，修改j次，且点i到1的距离为d的最大值。
考虑i的儿子2，d(2)要么为1(修改2的后继)，要么为d(i)+1(不修改2的后继)。
可令g[i][j][d]=max{f[i][j][d+1],f[i][j][1]}
那么我们可以得到方程:
(1).如果i不修改后继,那么除非点i本身到1的距离为1，否则d不能为1。
f[i][j][d]=max{g[s1][j1][d]+g[s2][j2][d]+…+g[st][jt][d]}+c[i]kd
(j1+j2+…jt=j)s1,s2…st为i的t个儿子。对于max可以再进行一次动态规划，用FF[i][j]
表示前i个儿子分配了j次修改的最大贡献，FF[i][j]=FF[i-1][k]+g[si][j-k][d]，max函数
的最大值为FF[t][j]。
(2).如果i修改后继
f[i][j][1]=max{g[s1][j1][1]+g[s2][j2][1++…+g[st][jt][1]}+c[i]k
(j1+j2+…jt=j-1)s1,s2…st为i的t个儿子。
最后考虑环的情况，由于环已经枚举确定了，所以答案就是：
max{f[p1][j1][0]+f[p2][j2+1++…+fplen][jlen][len-1]}(j1+j2+…jlen=m)pi为环上的点，如
图4.1答案就是max{f[1][j1][0]+f[2][j2][1]+f[3][j3][2]}(j1+j2+j3=m)。这里可以再用一次
动态规划解决。
因为每个点只会被背包计算一次，所以时间复杂度是O(lenn2m2)。因此可
以在时限内出解。近年与此题类似的题目大量涌现，如IOI2005《河流》、NOI2006
《网络收费》，这类题都是在树上进行动态规划，并且将本应该在点i计算的费用
转化到点i的子孙上。在规划i的子孙时假设未来的情况，并以状态的形式记录下
来，例如这道题是假设最近的修改点的位置，等到规划点i时直接使用过去假设
的决策。
【小结】
这类问题可以说是第一类问题的复杂版，同样是发现过去决策影响当前“行
动”的费用，同样是发现如果在当前状态记录过去的决策会使状态数过多，只能
将这部分影响在过去计算。不过，当前决策对未来“行动”费用的影响又与未来
情况有关，这时我们假设未来的情况，将不同的影响沿着不同的状态传递到未来。
三、总结
本文的四个例子，方程构造都是有一定难度的，其原因就在于当前“行动”
的费用受到过去决策的影响，而如果新增状态在当前假设过去的情况，状态数过
多。于是我们改变“时间观”，从过去考虑当前，即从当前考虑未来，把当前决
策对未来的影响计算到当前状态。
对于第一类问题，只需把对未来的影响算作当前决策的费用，保存在当前状
态。而对于第二类问题，需要假设未来的情况，把不同未来情况的影响保存在不
同的状态中，可以理解为把影响沿着不同的路传递到未来，待到未来决策时直接
使用。
当然，这两类问题变化是无穷无尽的，但只要我们善于发现，勇于创新，就
能构造出方程。
【感谢】
衷心感谢曹利国、周祖松老师在写这篇论文时给我的指导和帮助。
衷心感谢寻云波、李远韬、吴空、易茜、邓方丁、吴一凡等等同学给我的帮
助。
【参考文献】
[A]《算法艺术与信息学竞赛》——刘汝佳、黄亮，清华大学出版社
[B]WC2008孙辉讲稿
[C]BOI2007官方题解
【附录】
【附录A】
关于[猜想2.1]、[猜想2.2]的证明，来自BOI2007官方题解：
Letslookattheplayerpminwiththesmallestscore,whohastoendup
atpositionn.
Claim1:Ifpminismovedatall,itisoptimaltomovehimdirectlyto
theendofthelist.
Proof:Obviously,movinghimtowardsthefrontwillonlyincreasethe
costsofotherplayerstobemoved.Soassumehewillbemovedtowardsthe
endtoapositioni
possibilities:either,then?iplayersafterhiminthelisthavetobemoved
andtheircostsareincreasedby1(asopposedtothatpminwasmovedtothe
end),orpminhastobemovedagain,whichclearlyisnotoptimal.
Claim2:Ifpminismovedatall,wecandothisinthefirstmove.
Proof:FollowingfromClaim1,wealreadyknowthesecondpartofthe
movingcostsisfixed.Sotheonlyreasonnottomovepminfirstisthathis
currentpositiondecreasescausedbymovingotherplayers.Buttheseplayers
havetheirmovingcostsincreasedby1becausepminwasn’tmovedtothe
end.
Ifpminismoved,wehavereducedourproblemtothesameproblem
withn?1players.Ifpminisnotmoved,wehaveasimilarproblemwithn–
1playerswiththeadditionalrestrictionthatallplayersafterpminhavetobe
movedbeforepmin.
Letp0minbetheplayerwiththesmallestscoreamongtheremainingn
–1players.Wecanseethatitdoesnothelptomovep0minafterpmin,
becausethatwouldmeanwehavetomovehimagain,andwegainnothing
frommovinghimpastotherplayersstilltobemoved(foreachofthem,we
decreasedthemovingcostby1,andincreasedthemovingcostofp0minby
atleastone).Ifp0miniscurrentlyplacedbeforepmininthelist,bysimilar
argumentsasforClaim1wecanarguethatifp0minismovedatall,itis
optimaltomovehimdirectlybeforepmin.Also,Claim2stillworks.Sowe
areleftwiththecasethatp0miniscurrentlyplacedafterpminandhastobe
movedtowardsthefront.Ifthereareplayersbetweenpminandp0min,we
couldconsidermovingthemfirst.Ifwemovep0minfirst,thestartpositions
oftheplayersinbetweenareincreasedby1.Butifwemovesomeplayerin
betweenfirst,theendpositionwherep0minhastobemovedtoincreasesby
1,soitcan’tbebadifwemovep0minfirst.
So,wecanseethatbyusinginductionandtheargumentspresented
abovewecanprovethateachplayerismovedatmostonce,andtheplayers
canbemovedinascendingorderaccordingtotheirscore.
【附录B】
问题一源程序：
问题二源程序：
问题四源程序：
|
|
