关于NOI动态规划

关于动态规划：

动态规划的重要性我不必强调了，从06年开始或多或少年年有的一个科目。现在大家对动态规划的理解已经基本不错了，再强化一下更好。希望大家能够在开学半个月之内彻底解决本文所说的所有内容。因为开学考试的问题，不难为你们也不难为我。

Common动态规划基本性质是对于每个子问题是无后效性的。鉴于这个问题，对于一些图论问题，如果图是”有向无环图”，那么显然满足无后效性。如果图有环，那么可以考虑将环去掉，或者使用SPFA的动态规划。

1、理解与分析

读到题目首先肯定是要理解题目的内容。阅读理解是智商。但是OI的事实是很多题目都没能说清自己想要干嘛，再加上像我这样理解偏激的就可能遇见困难。碰见这样的题目不要纠结，问问同学这个题目想干嘛。题目的内容价值性将决定你做题的心情。

对于题目的分析，在你掌握一个OI科目的基础基础上，要将不会的问题转化为已经学过的问题解决。巧妙的转化可以顺利解决一些看似复杂的问题。比如下面这个问题，实际上你会做，只是你不知道。

题目1：地铁重组

问题描述

蒙提在暴风城与铁炉堡之间的地铁站中工作了许多年，除了每天抓一些矿道老鼠外，没有其他的变化。然而最近地铁站终于要扩建了，因为侏儒们攻克了建设长距离穿海隧道的技术难题，矮人们制造的炸药威力也有了很大的增强。于是，联盟决定修建通往诺森德的地铁。拥有常年的地铁站工作经验的蒙提被派往了新的线路上，他的工作是进行地铁重组。

如上图，在左边部分停靠着N节车厢，从右向左标号依次为1、2、……、N。中间有一个停车轨道，这个轨道上最多只能同时停放P节车厢。现在需要将左边轨道上的车厢驶入右边的轨道。每节车厢必须进入一次停车轨道进行检修，然后才能去右边的轨道。侏儒制造的每节车厢都有完整的动力装置，不需要依赖车头的带动。对于一个给定的停车轨道的大小P和左边轨道的车厢的数目N，蒙提想知道，这些车厢到右边轨道以后，有多少种不同的排列顺序。

输入格式

第1行：两个整数N,P。

输出格式

第1行：一个整数a，为排列顺序数除以4096的余数。

样例输入

3 2

样例输出

数据规模

对于70%的数据

1 <= N <= 500

1 <= P <= 300

对于100%的数据

1 <= N <= 2000

1 <= P <= 2000

看见这个题目你或许会一头雾水。题目大意是，给定一个栈，有N个数先后压入到栈中并不时弹出栈顶，最终得到的输出序列的方案数。没思路？看下面这个问题。

题目2：最小伤害

问题描述

把儿站在一个N x N的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。

输入数据

第一行输入一个正整数n。

以下n行描述该矩阵。矩阵中的数保证是不超过1000的正整数。

输出数据

输出最小伤害值。

样例输入

1 3 3

2 2 2

3 1 2

样例输出

数据规模

n<=1000

这两道题目几乎是一样的。不懂？翻到页后，便是这两道题的题解。不过建议你先考虑一下这两道题的关系，然后再决定是不是看答案。事实上连题目1的题解讲的都不如我解释的清晰，至少我看那个题解没看懂。

（本篇接下来的题目3的题解也在页后的题解中。）

2、计数与最优解

动态规划的基本目的分为计数与最优解。一些题目的目的是求得最优解，比如背包问题、奶牛的锻炼、乘法游戏、机器分配。一些题目的目的是求得总的方案数量，比如传球游戏、地铁重组（题目1）。

需要特别留意的是，动态规划问题（特别是求方案数量的问题）结果可能很大很大，通常碰见动态规划题，你需要判断结果可能的范围。如果觉得结果超过了maxlongint，那么你需要考虑使用高精度（NOIP2007TG矩阵取数游戏）或者使用longlongint(int64)（NOIP2011TG选择客栈）。

更一般的情况是出题者明确的通知你题目可能会超出正常的int表示范围，从而让你将结果取模一个固定的数值然后输出（NOIP2011TG计算系数）。这个取模的数值通常是一个质数，常见的有10007，1000000007，32767。

应对策略是，有：(a + b) % c == (a % c + b % c) % c，(a * b) % c == (a % c * b % c) % c。也就是说，可以每步计算出来的结果都取模这个固定的值，那么最终的结果也取模这个值。对于一般含有加法和乘法的题目中，仅采用这种方法就可以解决。如果运算中包含减法，那么就很有研究……在不同的环境（系统、编译器版本）下，负数取模会得到不同的结果，一些会得到一个最小的正数，一些会得到最大的负数，总之就是会出错。如果需要用(a – b) % c，那么一定要在取模之后将结果再加上c，然后再取模。这样做可以保证这个结果是一个正数，同样容易解决。如果结果中包含除法……对不起我写文章的这一天白天教师讲的时候没学明白这个问题总之对你们来说很复杂再想别的办法吧……

特别注意的一点，在取模的时候，如果要求你取模的数正好是2的几次幂，如32768或者4096，那么你可以采取与32767(4095)相”与”的做法来更高效的取模。这里只是一提，在讲状态压缩的时候讲提及这个事情，这里不过多讲述。

3、状态设立与方程

不知道你们是否读过一些动态规划的基础教程，里面可能会经常提到状态数目与状态转移方程。这个其实不适合对初学者首先提出，更容易吸引初学者注意力的是一些简单易懂而又有思想内涵的题目（如背包问题）。现在需要接触这两种东西了……比如背包问题的状态以及状态转移方程：

设F[i, j]表示在前i个物品中给定体积为j的背包所能获得的最大价值， N为总物品个数，V为总体积，value[i]表示第i个物品的价值，v[i]表示第i个物品的体积。

Ans：F[N, V]

F[0, j] = 0;

F[i, j] = F[i – 1, j], i > 1, v[i] >j;

F[i, j] = max(F[i – 1, j], value[i] + F[i –1, j – v[i]]), i > 1, v[i] <= j;

其中每个F[i, j]均为一个状态。那么总共有(N +1) * (V + 1)个状态，为O(NV)。每次计算一个状态消耗的时间只是判断并赋值，为O(1)。最终获得答案只需要读取F[N, V]的数值，也就是O(1)。那么这个背包问题总的时间复杂度为O(NV) *O(1) + O(1) = O(NV)。这就是动态规划分析时间复杂度的方式。状态数 * 状态转移复杂度 + 获得答案的复杂度。考虑复杂度的时候我们永远只保留最高次项，对于展开后的低次项全部舍弃掉。

对不同问题采取估计复杂度的方法不同。复杂度的估计不一定准确，对于一些问题，比如深度优先搜索、网络流，其复杂度极其难以估计，浮动性较强。而动态规划的问题一般容易分析出复杂度，并根据程序的时间复杂度预估自己会得到的分数。

4、预处理与优化

预处理就是在正式开始计算问题之前去预先处理一些问题的结果，在最终计算问题的时候减轻负担(NOIP2011TG选择客栈)。一些常见的预处理，比如有一数组a，共有N(N <= 100000)个数，在动态规划的进行过程中需要随时查询从a[i]到a[j]一段的区间求和。如果每次都枚举每个数来求和，那么需要时间为(j – i + 1)。而这样的话最坏情况是从1求到N，复杂度为O(N)。

预处理的方法是，预先求得数组s，s[i]代表从a[1]一直到a[i]一段区间内的和，有s[0] = 0, s[i] = s[i – 1] + a[i]，求得s数组消耗时间O(N)。那么需要查询a[i]到a[j]区间求和时，就可以直接用O(1)的时间求得s[j] – s[i]即为a[i]~a[j]区间求和（想想知道为什么吧～）。

对于复杂度降阶更直观的解释是，通过牺牲O(N)的空间来开数组，对于状态转移的复杂度与求得区间求和的关系由乘法变成了加法，降低的一个复杂度层次，效果极其明显。（区间求和的一些其他解决方式包括线段树、树状数组等，复杂度多数为O(logN)，不在NOIP考察范围内）

动态规划的优化，一般来说求得答案的复杂度较低无需考虑，那么需要从状态数量和状态转移的复杂度上下手优化。明显的例子不多，优化的主要手段同样是线段树和斜率优化等，不在NOIP考察范围内。

5、实现与调试

正确的在CCF提供的演草纸上写出了动态规划题目的状态转移方程，你还没有得分。“代码实现是智商”，如何将想法写道程序中才是关键。这一点没什么多说的，多练多写，不许手懒。不过，现在这个阶段不希望再有任何人对于基础语言学习有任何问题，如果你对现在同一教室学习的高一小孩讲课内容有疑问的话，说句不好听的，你可以走人了。

关于Interval动规的实现强调的一点是循环次序，和Common动规是不一样的。别的没什么特别。

关于代码调试由tomriddly同学负责讲授，大家热烈欢迎。

6、递归与复杂度

出门之前讲的两天课，动态规划的实现清一色递推。实话说我现在也不知道该先讲递推还是先讲递归。动态规划的基本实现方式分为递推和递归，递推重点介绍过了不再赘述。

关于递归，是代码实现最直观的一种方式。在函数中直接照抄状态转移方程，在主函数中直接给出需要求的Ans。递归相对于递推的好处，便是无需考虑问题的先后解决顺序，也就不存在循环次序问题，包括区间动规的循环次序问题。

裸的递归（深度优先搜索），对于背包问题(N, V <= 1000)来说复杂度就是2^n，推算方式是每个状态最坏的情况下是需要调用两个状态。这样在最好的情况下，当物品数为10的时候也布满了几乎所有的j(F[10, j])，那么接下来计算比10越大的i的时候状态的重复调用越明显。

而对于一个固定的问题F[i, j]，它的答案不随询问的次数而变化。也就是说，对于这个F[i, j]在第一次求出来的时候可以用一个数组f[N, V]记录F[i, j]的结果，第二次再次询问F[i, j]的问题的时候，可以直接取出f[i,j]的结果作为F[i, j]的结果，无需第二次计算。这种优化方式称为”记忆化”搜索。

对于记忆化搜索解决背包问题的复杂度证明：估计这种情况的复杂度，不能采用模拟递归的方式，而是想办法计算最多可能计算的状态数量。显然，函数F最多在调用(N + 1) * (V + 1)次的时候计算F所有可能的数值，这些数中的任何一个在第二次计算的时候均无需递归。也就是说这个时候的复杂度为O(NV)。这个复杂度是与递推一样的。

在一些类似于区间动规的问题中如果不能明确计算状态的顺序，那么完全可以采用递归的方式来绕过循环。相对的，递归的缺陷在于可能会“爆栈”。不过我想你们大概不用担心这个问题，NOIP的出题者不太可能卡你递归，这样做未免太残忍了。

7、滚动数组与方案记录

显然，滚动数组仅适用于递推。滚动数组的目的是优化空间复杂度，尽管在时间上多项式次数级别是一样的，但是在空间上节省一维数组，同时在一些特殊的题目中也减轻了时间上常数调用的负担（读取一个二维数组的值和读取一个一维数组的时间常数相差很多）。

滚动数组的使用条件是，有明显的状态层数并且下一层的状态取决且仅取决与其上固定的一层或几层的状态，并且不需要记录方案。在这种情况下，由于此前固定层数的状态计算完毕，已经被舍弃，无需继续保留。所以采用数组轮流滚动的方式可以大幅度减轻空间复杂度，降低空间复杂度的多项式次数级别。一般的能够采用滚动数组的题目，都是后一层取决于前一层。还是用背包问题来举例：

Ans：F[N, V]

F[0, j] = 0;

F[i, j] = F[i – 1, j], i > 1, v[i] >j;

F[i, j] = max(F[i – 1, j], value[i] + F[i –1, j – v[i]]), i > 1, v[i] <= j;

所有的F[i, x]取决且仅取决于数个F[i –1, x]。这样的动态规划问题可以采用两个滚动数组来优化。如果取决呈现单方向性，可以采用一个滚动数组来优化，那么背包问题的滚动数组优化方式方程为：

设F[j]表示在前i个物品中给定体积为j的背包所能获得的最大价值， N为总物品个数，V为总体积，value[i]表示第i个物品的价值，v[i]表示第i个物品的体积。

Ans：F[V]

F[j] = 0;

F[j] = F[j], i > 1, v[i] > j;

F[j] = max(F[j], value[i] + F[j – v[i]]), i> 1, v[i] <= j;

下面我们尝试写滚动数组的代码。因为这个代码没有演示过不知道大家理解的怎么样，下面就列出把一个非滚动的代码改成滚动的代码的过程。理解试试看。

之前的核心代码大概是（变量、数组定义，读入，F[0, j]预处理省略）：

for (int i = 1; i <= N; i++)

for(int j = 0; j <= V; j++)

if(v[i] > j)

F[i][j]= F[i – 1][j];

else

F[i][j]= max(F[i – 1][j], value[i] + F[i – 1][j – v[i]]);

那么按照这个状态转移方程，修改之后去掉第一维的数组即可（第二层循环的次序需改变）：

for (int i = 1; i <= N; i++)

for(int j = V; j >= 0; j--)

if(v[i] > j)

F[j]= F[j];

else

F[j]= max(F[j], value[i] + F[j – v[i]]);

额。。看看这个代码是不是发现了什么亮点。。

F[j] = F[j]

………………

for (int i = 1; i <= N; i++)

for(int j = V; j >= 0; j--)

if(j >= v[i])

F[j]= max(F[j], value[i] + F[j – v[i]]);

j >= v[i]的情况下才执行接下来的更新。而在其他的情况下没有任何改动。也就是这样：

for (int i = 1; i <= N; i++)

for(int j = V; j >= v[i]; j--) //此处循环条件变化

F[j]= max(F[j], value[i] + F[j – v[i]]);

再看最后一行。F[j]从F[j]和value[i] + F[j – v[i]]中取最大值，换句话说，如果后者比前者大，那么更新前者，否则无变化。那么更好的方法是：

for (int i = 1; i <= N; i++)

for(int j = V; j >= v[i]; j--)

if(F[j] < value[i] + F[j – v[i]])

F[j]= value[i] + F[j – v[i]];

这种代码差不多是最优的写法了。还有一种更好的方法是采用一个自己定义的upd_max函数再降低常数复杂度。暂时不介绍了。

关于方案记录，基本方法是在转移状态的时候，记录当前状态是从哪里转移过来的。这样在最后F[N, V]的时候就能沿这一趟线循环回来，依次地读取到每一步的最优决策。同样的方法适用于一些基于动态规划思想的图论方法，如最短路记录方案。由于方案记录问题需要第二次调用所有状态，所以不能采用滚动数组。

题目3：阿鲁高的阴谋

问题描述

我尝流连于格雷迈恩之墙，叹息着轻抚隔世的沧桑。

我曾徜徉于洛丹米尔的水，飘离在腐败的气息之上。

卫道士有卫道士的避风港，叛节者有叛节者的理想乡。

魔法师有魔法师的墓志铭，造物主有造物主的礼拜堂。

影牙城堡的主人，执着于疯狂。

牙将被诅咒磨砺，影终被黑夜深藏。

我曾抬头看着银松穹顶的冷光，血月的辉耀隐约中露出寒芒。

巨大的引力牵动着星辰的轨道，谁又看得到这个世界的真相。

在第三次战争中，达拉然被燃烧军团彻底催化。曾经是肯瑞托的一名成员的阿鲁高，在不断的失败和恐惧中，召唤了远古的恶魔——贪婪而又凶猛的沃根。沃根恐怖的力量很快清理了附近的亡灵天灾，但是它也开始对肯瑞托发起了攻击。可悲的是，阿鲁高也堕入了恶魔力量的深渊，他把附了沃根魔法的手腕强加在自己的朋友手上，让他们变成了奴仆。一个夜晚，阿鲁高带领沃根悄悄穿越格雷迈恩之墙，进攻了影牙城堡。原来辉煌的城堡，顷刻间被阴影和血腥味所笼罩。隐身于城堡内高高的塔顶不断扩充自己的军队，幻想有一天可以成为这片大陆的主人。终于有一天，巫妖王剥夺了阿鲁高死亡的权利，把阿鲁高变成了他当年痛恨的敌人，亡灵天灾。在诺森德，阿鲁高建立了血月神教，领导狼人们成为了天灾军团的爪牙。在灰陵的海岸上，阿鲁高建立了第一个据点，并让手下变成人形骗取了联盟军团的信任。

银溪镇的追随者们为阿鲁高制造了一个船，用于在海岸上扩张。在漫长的旅途中，阿鲁高必须消耗法力创造结界以存储燃料。在途中每一天，阿鲁高都可以驶到一个联盟港口骗取燃料，代价是消耗法力维持幻象。阿鲁高的目标是寒冰皇冠，要航行T天才能到达。由于天气和海域的不同，每天航行所需的燃料消耗也不同。每天都可以到达一个联盟港口，骗取一些燃料（也可以不去，从结界中取得燃料补充所需，注意，每天的消耗必须被满足），骗取每个单位燃料需要一定的法力消耗。如果骗取的燃料除供这一天消耗外还有剩余，则必须把它存到法力结界中，但是限于结界规模，只能把不超过V的燃料存储到结界中。在结界中存储的每个单位的燃料每天会消耗掉阿鲁高的W点法力值。为了留有足够多的法力，阿鲁高必须尽量地减少法力消耗。请你算出阿鲁高到达目标最少的法力消耗是多少。

输入格式

第1行，四个整数，航行的天数T，结界的最大存储量V，每个港口的库存A，结界中每存储一单位燃料一天的法力消耗W。

第2行至第1+T行，第k+1行有两个整数，分别表示第k天的需要的燃料N[k]，抢夺第k天到达的港口的每个单位燃料的法力消耗B[k]。

输出格式

第1行，最小的法力消耗。

第2行至第1+T行，第k+1行有一个整数，表示第k天到达港口后抢夺燃料的数量。如果有多种解，使每天抢夺的燃料数组成一个序列，所有这些序列构成一个集合，对这个集合进行第一位为第一关键字，第二位为第二关键字，……的多关键字排序，输出其中最小的一个即可。

样例输入

2 5 10 5

5 20

3 30

样例输出

175

样例说明

在第1天骗取8个单位燃料，法力消耗8*20=160。5个用于当天直接使用，3个放入结界，存储法力消耗3*5=15。在第2天不需骗取，直接使用结界中的3个单位燃料。所以总法力消耗为160+15=175。

数据规模

1<=T<=1000

1<=V，A，W，B[i]<=100

1<=N[i]<=V

8、联想与停止联想

对于很多题目，做完了之后可以多考虑考虑，如果这个问题扩展了更广泛的条件应该怎样做。比如说背包问题，扩展出来了很多其他限制之后研究更广泛的问题，有了背包问题九讲，大家有兴趣读一读。最小伤害(题目2)的问题就是方格取数，为一取方格数。拓展，NOIP2008TG传纸条类似于二取方格数，区别在于传纸条不能第二次走走过的格，但是二取方格数可以走走过的格，走过的格得到的结果是0。也是在状态转移方程上有细微的判断变化。如果是三取方格数，那么继续对方程的维数扩展即可，方法类似。建议大家试着写一下最小伤害(题目2)和NOIP2008TG传纸条这两道试题。……不过如果是N取方格数，N由输入给出，该怎么做？类似于这种题目，数组维数不适合轻易变化，这种联想就不合适了，至少N取方格数不在NOIP的考察范围之内。更多时候，考试时候碰见的题目只需要你算出考场上的题目对应的范围即可，不必要在考试的时候给自己出难题，不要因为追求更好的做法而死憋。不过考场下练习的时候可以多多思考，锻炼自己的思维能力。（N取方格数这个题目需要使用网络流来解决）NOIP2010TG乌龟棋、NOIP2010TG关押罪犯也同样，如果将乌龟棋的牌数扩展为M个，就难以解决了。不过关押罪犯的监狱数量扩展倒是有一种更好的解决方法，具体内容不太清楚，不过确实是CA72原创。总之不要太难为自己。

本文的所有内容均为口述，没有给出任何代码。代码实现的能力需要锻炼……lemon_TsyD第一次教我SPFA求最短路的方式的时候，他只是说了SPFA的计算方式，回去我就写出来了（尽管写的有问题……但是起码能过题了）。希望大家能够逐渐锻炼出来这种能力。调试能力和编写能力都很重要。

其中内容的错误还望指正……之前发现代码写错了，忘了第二层循环倒序循环了。

题目2：

F[i, j]表示到第i行第j列这个格为终点所获得的最小伤害。那么：

Ans: F[N, N];

F[i, j] = 0, i == 0 || j == 0;

F[i, j] = min(F[i – 1, j], F[i, j – 1]), 1<= i, j <= N;

这个题目很简单了。

题目1：

我们注意到，对于任何一个时间点，出栈的次数永远小于等于入栈的次数。那么观察这样的一个图：

从左上角走到右下角的方案数是多少呢？

向下走一次，代表入栈一次；向右走一次，代表出栈一次。由于出栈数必须小于等于入栈数，灰色区域不能抵达。

这只是在没有P限制的情况。在有P限制的情况只需要限制两者的差就可以了。

设F[i, j]表示入栈i次，出栈j次的时候状态的方案数，设m = 4096

Ans: F[N, N];

F[i, j] = 0, i == 0 || j == 0 || i < j|| i – j > P;

F[1, 1] = 1;

F[i, j] = (F[i – 1, j] + F[i, j – 1]) % m,i != 1 || j != 1, i > 0, j > 0, i >= j, i – j <= P;

问题解决。

题目3：

今天太晚了累了……题解照抄原版了，不自己手工给你们打了。

阿鲁高的阴谋

本題的变量比较多，有些麻烦。我们再来理清一下船、联盟港口、结界的关系。

船每天都有一个燃料的需求，而这个需求需要从港口或者结界来补充，掠夺港口需要一定的代价，而携带燃料同样有一定的代价，且携带燃料有一个上限。

更直白一些，需求者为船，商品供应者为港口，而结界就是一个燃料仓库。

由于在每个港口都需要做一个决策，那就是要上岸掠夺多少燃料。这样，就让我们看到了问题的解决思路

多阶段决策的动态规划

在每个港口，我都需要做一个掠夺多少燃料的决策，我们把状态设为(k,s),k表示这是第几天，s表示在这一天的开始，魔法结界中保存的燃料数。令f(k,s)表示第k天开始时结界中存有s单位燃料时，从第k天开始至旅程结束的最少魔法消耗。

如果一个状态为(k,s)，那么如果在第k天掠夺x单位燃料。那么，下一个阶段(k',s')即为(k+1,s+x-N(k)) (N(k)表示第k天的消耗)，而从(k,s)跳转到(k',s')，连结这两个状态的法力消耗为B(k)*x+W*(s+x-N(k))，其中，B(k)*x为抢夺燃料的法力消耗，W*(s+x-N(k))为保存燃料所需的法力值。

由于每个港口的存储量A与魔法结界的最大存储量V的限制，我们必须保证x<=A , s+x-N(k)<=V

由于需求必须被满足，则0<=s+x-N(k)。

综上，得出

N(k)-s<=x

0<=x<=A

x<=V+N(k)-s

同时，s本身也必须满足实际的要求(0<=s<=V)‏

通过上述分析，我们可以写出状态转移方程

f(k,s)=min(f(k+1,s+x-N(k))+B(k)*x+W*(s+x-N(k))‏

MAX(N(k)-s,0)<=x<=MIN(A,V+N(k)-s)‏

初始状态：f(k+1,s)=0 (s=0..V)‏

目标状态：f(1,0)‏