线性动态规划做题笔记

动态更新中

P1541 乌龟棋

题目链接

这个题虽然是个绿的，但是还有总结一下的价值的

首先我们可以想到一个非常显然的做法就是：每一种卡片我都记录到状态里面，然后记录一下当前位置

这样时间空间复杂度都会炸

那么就可以很显然的发现。。。位置减去三种卡片对应的走过的位置就可以推出用第四种卡片走的距离或者说用了几张第四种卡片

然后就可以省掉一维

（有的地方会有一点点的细节。。。不过也没有大碍

（只要不把这个题想成背包就会很好做……

初始化还是比较重要的（下面那道题题我就是抄的题解的初始化

SP703 SERVICE - Mobile Service

题目链接

这个题和上面那个题还是有着异曲同工之妙的

但是比上面那个题难一点。。。

首先朴素的dp方法：把所有的状态存进去

就是1000个申请，200个a的位置，200个b的位置，200个c的位置

会炸。。。

那么就开始分析题目性质：

我们会发现：在第i个申请结束之后是一定会有一个人的位置在p[i]的（重要

那么我们可以压缩掉一维空间（还有时间

设$f[i][x][y]$为第i个申请，一个人在x，一个人在y，一个人在p[i]的方案数

那么……就可以转移：

$$f[i + 1][p[i]][k] = min(f[i + 1][p[i]][k], f[i][j][k] + w[j][p[i + 1]]);$$

然后就是初始化的事情了：（我写博客还是要把初始化写上的

$f[0][1][2]$是初始状态，设为0，其他都设成inf，由于我们有个p数组的限制，那么我们就可以把p[0]改一下，p[0]改为3

完啦

SP15637 GNYR04H - Mr Youngs Picture Permutations

好题！（但是机房里基本没人做这个题是什么鬼啊

这个题猛然一看完全没有思路叭……

但是我们考虑dp的时候……如果我们需要满足题目中的限制的话，改变一下dp的方式：

我们考虑向序列中插数，从小往大插

那么就会有一个性质：从小往大插就说明当前插得数一定是最大的

那么就说明：一定满足条件！

那么我们考虑插数的前提条件是什么：

我们可以往一个位置上面插数，手下我们要保证上一行的当前列是有数的（这个数一定比当前数小）（并且第一行随便插

如果上一行的这一列没有数，后面一定会插进来一个数，那个数肯定比当前数大，就会不符合题意

并且我们还要保证这一行没有插满

那么我们设dp状态：由于最多只有5行，所以我们就设dp函数$f[i][j][k][l][p]$表示第几行站着多少人

然后转移就可以了

初始化的话：$f[0][0][0][0][0]=1$就没了

（记得多组数据的初始化

P2943 [USACO09MAR]Cleaning Up G

题目链接

这个题是真的好…

首先我考虑一件事情(大大缩短时间的事情:

一段连续的区间我们最多只会给他根号n个机会(根号n个不同的数字

因为如果我们把n个数字都变成自己一个人一次吃饭的话答案应该是n,所以答案绝对小于等于n

那么我们设pre[i]表示上一个与在i位置的食物相同的食物位置，

nex[i]表示下一个，

last[i]表示种类为i的食物出现的最后一个位置，

如果i点没有上一个则pre[i]=0，没有下一个则nex[i]=n+1，

然后进行求解:

判断时，如果pre[i]<pos[j]，说明i这个点在[pos[j],i-1]中并没有出现过，

设cnt[j]为pos[j]对应的出现次数，则cnt[j]++；

当cnt[j]>j时，显然pos[j]应该右移，如果nex[pos[j]]<i，说明在pos[j]这个位置的食物在区间中出现了不止一次，

则删除它后不同个数仍然不变，因此要不断右移，直到nex[pos[j]]>=i，此时删除它后不同个数减一

完事

P2389 电脑班的裁员

这个题是个小蓝（其实$n^3$的暴力dp就可以跑过去

我在这里简述一下$n^3$和$n^2$的方法

$n^3$

我们这么考虑：

我们应该是有一段一段连续被选的区间，但是这几个区间之间是可以连续的

那么我们就可以转移的时候暴力一点点 ：

$f[i][j]$为前$i$个数（第i个数可选可不选）（后面会说这个可选可不选的事情）划分为最多j段的时候的最大答案

那么我们考虑一下枚举最后一段的左端点：

我们首先认为左端点k到右端点i这一段区间的所有值都必须要选

那么转移就是：$f[i][j]=max(f[i][j],f[k][j-1]+sum[j]-sum[k])$

后面的sum是前缀和

然后，因为我们的几个段之间是有着断点的，所以我们要考虑第i位选不选的问题：

那么我们就可以发现，如果说i不选的话，$f[i][j]$就相当于是$f[i-1][j]$了

又因为我们求的是最大值，所以我们直接max一遍就可以了

$n^2$_$1$

首先我们上面的算法复杂度有点高。。。但凡数据是1000我们就跑不过去了

那么我们考虑优化

我们会发现上面的转移方程：我们的左端点对应的$f[k][j-1]-sum[k]$的决策范围是只会增大不会减小的（因为我们是在从前往后枚举

那么我们就可以开一个数组：$cnt[j]$表示第二维是j的决策范围中的最大值，每次枚举到一个j的时候都把他更新一遍

这样时间复杂度就可以降低一个n

$n^2$_$2$

我们会发现上面的做法的空间复杂度是$n^2$

如果我们变化一下头脑就可以让空间复杂度剪掉一个n

我们设$f[i][j][0/1]$表示前i个数里面划分为j段，不一定取第i个和不取第i个的方案数

然后我们就知道转移方程：

$g[i][j][0]=max(g[i-1][j],f[i-1][j-1])+a[i]$

$f[i][j]=max(f[i-1][j],g[i][j])$

P5020 [NOIP2018 提高组] 货币系统

非常简单的一个背包题

题意似乎是b数组被a数组所包含的。。。

首先我们考虑：如果说原来的货币系统中有一个数字是可以被其他数字表示出来的，那么我们就可以把这个数字去掉了

并且我们不用考虑一个数被表示出来删掉之后会有一个数不被表示出来（因为我们既然可以把这个数字表示出来就说明并没有什么毛病

所以我们跑一遍完全背包之后统计一下有那些数字是可以被别的数字所表示出来的

那么我们直接求出来每一个数被表示的方案书，如果大于1（就是说除了他自己可以表示出来他自己之外还有别的人可以表示出来他）那么就把他删掉

最后统计还剩下多少个数字就可以了

P4597 序列 sequence

这个题（有着多倍经验）

这个题非常的玄学。。。

（一个小结论题）（但是可以用dp写弱化版

先讲一下弱化版把：

首先我们设dp的函数$f[i][j]$为把前面i个数字的最大值变成排名为j的数的最小代价（使得前面也是合法的序列

那么方程就可以被我们搞出来：

$f[i][j]=f[i-1][j]+abs(a[i]-a[j])$

$f[i][j]=min(f[i][j-1])$

方程的含义就是我们把当前这个数变成排名为j的数的最小答案（$f[i-1][j]$是代表我们把前i-1都不小于排名为j的最小答案

那么我们就把当前的数字强制变成排名为j的数（因为并不知道前面的数都是多少，由于是单调不降，所以前面一个数是可以和当前数相等的，所以说如果我把这个数变成比排名为j的数要小的数就会不对

所以要取min

加强版：

那么我们维护一下前半部分的最大值，（如果最大值比当前数大，加一下当前值和最大值的差就可以了（以上是做法

分析：

我们找到前半部分的最大值y，如果这个值比当前的数x要大的话，我们就需要找到一个基准值，让y降下去，x升上去，既然是要满足不降，那么y要比x小于等于，那么就让他们两个等于就可以了

但是如果说y前面的数的最大值比较大怎么办呢，我们让y和x都变成那个数就可以了，代价不变

（但是事实上我并不懂这个做法的正确性

加强版：P2501 [HAOI2006]数字序列

有一个小结论：一个区间如果两头是固定的，并且是单调不降的，那么把它变成一个单调不降的序列的话，最小的代价一定为：从中间某一个点断开，前半部分和第一个数一样大，后半部分和最后一个数字一样大（然后求代价

这个题就用到了上面的那个小结论

我们首先是做第一问：

由于是要单调不降，那么我们会发现：

$a[i]-a[j]>=i-j$这样也就相当于是：

$a[i]-i>=a[j]-j$

那么我们就可以把原序列转化一下转化成是求：序列$b[i]=a[i]-i$的最长不下降子序列，然后用总数减掉

第二问：

我们在求最长不下降子序列的时候是可以处理出来一些东西的：每一个长度的不下降子序列的末尾

那么我们存一下，就相当于是：我们把转移的过程进行联编，比如说我在长度为i-1的末尾x，如果x<当前的y的话

就把x向y连一条边（当然了我们是求出来那个末尾所对应的最长不下降子序列

然后，我们就把每一段的pre[i]（就是转移到i的那个地方）到i这个地方，我们把这段区间里的最小代价算一下，然后dp一下就好了

[P3336 ZJOI2013]话旧

不想写。。。太恶心了。。。分类讨论。。。

[P4158 SCOI2009]粉刷匠

挺好nan的一道题

（题目的意思中：刷错和没刷是一种类型的东西，所以我们为了最优策略直接选择所有的格子都刷一遍

首先我们会发现我们可以先单独处理每一块木板（因为都是相互独立的

然后我们在处理完之后进行一下合并

我们先考虑一块木板的情况：

我们设$f[i][j]$为前i个格子里刷了j次，那么转移的时候就先考虑一下前面的j-1次都刷在了哪里

如果说我的前面的j-1次都刷在了前k个格子里，那么我们就相当于后面k+1~i的所有的格子都在一次粉刷中被刷了

那么我们就可以得到转移方程：

$f[i][j]=max(f[i][j],f[k][j-1]+maxv(k+1,i))$

其中maxv函数代表的是这段区间中最多的颜色的数量

合并的时候很简单：

我们设$g[i][j]$表示前i个木板刷了j次之后的最大的价值，那么我们就可以发现，我们把前面i-1个木板的所有的价值看成一个个物品， 再把当前第i个木板的价值看成一个个物品，然后做一次背包就可以了（刷了多少次是体积，价值就是价值

P1156 垃圾陷阱

首先我们需要把整个数组按照时间顺序来排一遍序（废话

然后我们就设数组$f[i][j]$表示前i个垃圾，当前高度为j的剩余最大生命值

那么我们会发现只有两种可能了：一种是吃了不放，一种是放了不吃

然后我们对应的进行转移

当然转移的时候是需要一点点判断的

就比如说（有没有死，是不是已经可以上去了

P4290 [HAOI2008]玩具取名

首先我们可以把那一堆字母存成数字对吧。。。

我们首先是存一下都有哪些的二元组是可以转化成那个数字的，这个在样例输入的时候是可以搞出来的

然后我们就可以进行区间dp了

设dp数组$f[i][j][1/2/3/4]$表示$i->j$区间内的所有数字可不可以转化成$1/2/3/4$这几个数字

我们在存一个flag数组$flag[i][j][k]$表示二元组$i,j$可以转化成k

那么dp方程就可以很快地求出来了：

$f[i][j][k]=(f[i][l][p]~and~f[l+1][j][q]~and~flag[p][q][k])$

如果说左区间可以转化成一个数字，右区间可以转化成一个数字并且这两个数字拼起来是可以转化成当前我们像要求的这个数字的话，说明是可以转化过去的，那么我们就把当前的f数组的值设为1（f是一个bool数组

然后我们对每一个数字都判断一下整个区间能不能一起转化成这个数字，如果能就输出（记得特判无解的情况

P1622 释放囚犯

（本人写区间dp的时候比较喜欢写记忆化搜索

我们首先把一个0和m+1插入到原序列里面去，这样保证我们在求dp的时候方便

仔细读题我们可以发现，如果说我们把一个人放出去了，那么它会产生的代价就是他所在的联通的区间的人数减一

那么我们插入一个0和m+1的时候就相当于是插进去了两个已经被放出去的犯人，既然已经被放出去了就相当于是不连通了

并且这个题非常符合区间dp特点的一点就是，我们如果把一个区间断开之后，就要算单独断开的两个区间的价值了

我们会发现，我们直接在给定的序列上做就可以了并不需要把给的几个数字插入到一个长度为m的序列上

那么我们设dp数组$f[i][j]$表示i-j区间的最小代价（小区间和大区间相对独立

那么我们就枚举一下小区间的断点，然后计算更小的区间直到边界

$f[i][j]=max(f[i][k-1]+f[k+1][j])+a[j]-a[i]-2$

方程里的减二自己手模一下就知道了

[P5851 USACO19DEC]Greedy Pie Eaters P

Y1S1这个题还挺好的

我们设一个p数组$p[i][j][k]$表示一个左端点右端点都在i-j之间的区间，并且可以以k为断点的区间的最大价值

然后f数组$f[i][j]$表示区间i-j里面的最大价值

那么转移方程就出来了：

$f[i][j]=max(f[i][k-1]+f[k+1][j]+p[i][j][k])$

[P2967 USACO09DEC]Video Game Troubles G

先说算法：线性dp，背包

我们考虑一下，每一台电脑机子和游戏是相互独立的，那么我们就可以求一下每一台机子的方案，然后再把所有的方案合并一下就可以了

那我们每一台机子的价值就是跑一遍01背包咯

先跑一遍普通的01背包，但是因为机子是没有价值但是有花费的，所以它并不能跑到背包里，但是还必选，那么说明我们要把背包的体积减小

[P2938 USACO09FEB]Stock Market G

首先我们考虑题意的时候我们会发现，对于每一天来说，股票的购买和卖出都只有三种情况：

1. 不买不卖
2. 卖掉昨天的
3. 今天买，留着以后卖

那么我们会发现第三种情况是可以转化的：如果说我们今天买了之后明天不卖，就相当于今天买了，明天卖掉，在重新在同一天买回来，就可以转化成第二种

那么我们就变成了只需要考虑连续的两天了，就可以线性做了

设出函数：$f[i]$表示手中有i钱数的时候，我可以最多赚多少钱

然后每一次更新一下手中钱的最大值

每一次计算一下利润，然后加到答案里，利润为0就相当于啥都不干

[P5662 CSP-J2019] 纪念品

一个很像的题，但是这个题的代码交过去不能过（因为n和m是倒过来的