2.1.2决策更新状态

当一个状态计算完毕，那么这个状态就 自然的成为了后面状态选择的一个决策， 于是我们可以在刚产生这个决策的时候 更新所有可能用到这个决策的状态。 可以说这是一个逆向行为的过程。 大多数时候正向方式和逆向方式是差不 多的，或者正向方式优于逆向方式，当 然也有例外，因此需要我们自己根据实 际情况灵活选择。
浅谈动态规划优化
2009曹文信息学奥林匹克夏令营 Author: Will
简介
动态规划优化的主要方法： 1、降维（优化状态） 2、优化转移 3、常数优化

1.降维

降维是一个通用的说法，其实质就是通 过改变动态规划的状态含义，或者抛弃 一些冗余状态环节，达到减少状态，加 速动态规划的目的
1.1.1.1思路一
按照基本的状态压缩动态规划模型进行 解答。 opt[K][S]表示已经放了前K行，并且每 一列是否有车的状态为S（S为一个0/1 的2进制序列，那一位为1则表示对应一 列已经放过了一个车）的合法方案的数 量。 比如opt[2][(101)2]即表示前2行放了车 且第1，3列有车的状态。

2.3.1.2优化
我们不妨换个思路，为什么要去纠结于 之前的状态呢？ 当我们做了一个决策之后，对后面的影 响我们是知道的，为什么不能把握这一 我们清楚的信息呢？ 道理很清楚：

2.3.1.2优化
每次决策后，我们将这一次移动对所有 我们还没有得到的小球产生的费用损失 都在决策时计算。 我们可以看作小球都没有动，只是在我 们每次决策是损失了一些价值。 假设当前移动花费了时间T，我们还没 有得到的小球的速度和是SV，那么损失 的代价就是T*SV/1000

2.4.1.2分析
首先我们花O(N)的时间枚举左下角c 所有需要计算的点都以点c为原点建系 假设坐标为x[i]和y[i] 按极角排序后，我们要求的就是

x[i] y[ j] y[i] x[ j]
i 1 j i 1
N
N

不难得出一个O(N3)的算法
2.4.1.3优化
2.4.1例题
Triangles (POI07-08 StageIII) 给定平面上N<1000个点，则显然会构 成N(N-1)(N-2)/3个三角形 求所有这些三角形的面积和

2.4.1.1预备知识
首先必须要知道叉积…… 向量a=(x1,y1)，b=(x2,y2) 则有： a × b = x1 * y2 – x2 * y1 =|a||b|sinΘ Θ为有向角度 因此只要保证方向为正，那么向量a和b 组成的三角形面积即为(a × b)/2
2.2.1.1分析
代价f我们可以边转移边计算。 我们从i开始从后往前枚举j，那么我们 显然每次只需要O(N)的代价就可以计 算出当前的f。 动态规划的时间复杂度为O(rsM2) 算法的总体复杂度为O(C(N,r)rsM2)

2.2.1.2优化
1.预处理出sum[x][y]数组，记录矩形 (1,1)-(x,y)中每个格子的工作量之和。 则对于任意矩形，我们都可以在O(1)时 间内计算出部分和。 2.搜索完行的拆分之后，我们预处理出 所有f数组。 计算f数组的时间复杂度为O(M2r) 此时动态规划复杂度为O(M2s) 总复杂度降为O(C(N,r)M2(r+s))

2.2.1.1分析

简单的想法是首先枚举横向如何对土地 进行分割，然后再对纵向进行动态规划。 枚举部分我们不多说，这里共需要 C(N,r)的时间，我们用数组lis记录分割 情况 关于动态规划，不难得到如下方程： opt[i][k]表示第i个竖线为第k个分割线。 转移比较简单 opt[i][k]=min{max(opt[j][k-1],f(j,i))}

1.2.1例题
poet(NOI2009 day1 p2) 有N个诗句，要每个诗句有一个长度Li， 要将其排版，一行可以放若干诗句并且 每句诗中间用一个空格隔开，有一标准 长Len，每一行的难看度是当前行长度 C与Len之差绝对值的P次方。 求一种最好看的排版方式使得总难看度 最小。 N<10000 L<200 1<P<1转移稍有不同 opt[k+1][S]=opt[k][S]+opt[k][S+1]*(S+1) 此时时间复杂度为O(NM) 空间复杂度为O(NM) 问题得到了解决 可见对问题透彻的分析是得出最有效规 划方式的前提。

1.2抛弃冗余
很多时候一些状态是不需要的，或者某 些维是可以合并的。 经过合理的分析我们可以抛弃一些冗余 信息，减少状态，加速转移。

我们给式子做一个变形
x[i] y[ j] y[i] x[ j]
i 1 j i 1
N
N

我们用Sy[i]记录y[i]到y[N]的和，Sx[i]记 ( x[i] y[ j] y[i] x[ j])
i 1 j i 1 j 1 录x[i]到x[N]的和，那么要求的就是

2.1优化转移方式
基本的转移方式共有两种 1、通过状态选择决策 2、通过决策来更新状态

2.1.1状态选择决策
对于每个状态会有一些决策来选择，我 们从中选择一个最优的决策，来实现规 划的过程，并完成了当前这一状态的计 算。 可以认为这是一个正向过程。 一个简单的例子 opt[k]=min(opt[i]+1|A[i]<A[k]) 这是一个不下降子序列的动态规划方程 不难得到这个方法O(NlogN)转移方式

2.3.1.1分析
由于所有小球的x坐标是不变的，因此 我们按照x坐标将小球排序。 观察一个性质： 我们获得球必然是一个连续区间。 因此不难得出动态规划表示方法： opt[L][R][0/1]表示获得球的区间是[L,R]， 同时此时飞行器在左边/右边球所对应 的x坐标。

2.3.1.1分析
但是，如何计算代价呢？ 考虑到一个很好的性质：飞行器的移动 速度是单位速度。 一种简单的方式是增加一维时间： opt[L][R][T][0/1]表示时刻T此时的状态。 可以使用队列保存可行状态，再使用更 新状态的方法进行转移。

2.3.1.2优化
现在问题的关键在于如何快速的计算费 用。 我们现在纠结的问题在于，我们并不知 道之前我们是如何行走的，所以如果没 有T，我们并不知道当前我们面对的球 到底是多少价值。

2.3 费用提前计算

在动态规划问题中很多时候计算转移代 价成了我们一个很棘手的问题，有些时 候我们可能要花费很多的力气来计算某 一些特定状态下的费用（比如边界状态 等等） 其实很多时候我们可以用一些方法，把 费用计算花去的时间平摊到其他的地方， 从而优化动态规划
2.3.1例题
Sue的小球(sdtsc 2008) 天空中有N个坐标为(xi,yi)的小球，并会 以vi速度匀速下降，这个小球的价值就 是其y坐标的1000分之一 你有一个在x坐标轴上滑行的飞行器， 可以以单位速度在x轴上平移，只要和 小球到同一x坐标就能收获那个小球。 假设你一开始在(0,0)，并且希望收获所 有小球，问可能的最大收益是？ N<1000

1.2.1.1思路一
由于标准行长L很小我们不难想到一个 如下的动态规划方法： opt[K][S]表示排版了前K个句子，并且 当前行长是S。 对于每个状态转移就是枚举是将这个诗 句放在行末还是换行。 有一个问题是： 如果一个诗句过长怎么办？？？那我们 也将数组下标开的很大么？？

1.2.1.2思路二
1.1转变思路
很多时候，当得出某种动态规划模型的 时候，不要着急动手，而是需要仔细思 考一下，是不是有更好的状态表示方法 多积累经验，同时又不能拘泥于死板的 模型理论，要有创新意识。

1.1.1例题

给定N*M的空白棋盘，在其中放任意放 车（可以不放），要使得放在棋盘上的 车两两不能攻击，求方案总数MOD P 的值。
2.2 预处理

预处理就是将动态规划中常用的一些计 算环节预先处理好，方便动态规划中重 复用到，很多时候利用这种并行计算的 问题是可以大大降低算法复杂度的。
2.2.1例题
Grid(BOI2008) 有分成N*M格的土地，每个土地有一个 工作时间，现在可以将这些土地分成 (r+1)*(s+1)块，每块由一个工作人员来 完成工作，问最快能多长时间完成全部 格子上的工作？ r<N<18 s<M<18
仔细分析，不难发现，第二维状态是没 有用的。 我们需要知道只是每一行最后一个诗句 是那个就可以了，并不用关心每行具体 多长。 我们抛弃第二维： opt[K]表示安排了前K个诗句并且第K个 诗句在行末所能获得的最小难看度。

1.2.1.2思路二
那么转移就是 opt[K]=min(opt[i]+cost(i+1,K)|i<K) cost(i+1,K)表示第i+1到第K个诗句放一行 的难看度。 那如何利用L<200的条件呢？ 用Sum(L,R)表示第L到第R个诗句放一行的 总长 如果对于i，存在j使得Sum(i,j-1)>L且 Sum(j,K)>L则所有i之前的决策都是无用的。
2.1.2.1例题

给N*M的存在一些障碍的棋盘，在其中 放置1*2的多米诺骨牌，问合法的放置 总数MOD P是多少。
2.1.2.1.1说在前面
我们这里先介绍一种对于状态压缩动态 规划转移和状态表示的一般方法——按 格（点）转移。 opt[x][y][S]表示当前决策格为(x,y)同时2 进制状态S表示当前扫描线上每个格子 是否被覆盖的状况。