动规个人总结-DP-动态规划

i207M · 2018-04-29 17:55:17 · 个人记录

~~留坑待填~~

给定01矩阵求最大国际象棋棋盘方法

对于01矩阵，求形如国际象棋的最大棋盘位置的方法（eg.LG1169）是：将横纵坐标和为偶数的点取反，即：

    a[i][j] ^= (i ^ j) & 1

然后求最大同色正方形/矩形

求最大同色矩形

求出每个点向上最长延伸多长up[i][j]；利用单调队列求出这个长度最多向左向右延伸多长，统计答案；

给定序列 a[1...n]，最少修改几个位置可以变成上升序列

令 a’[ i ] = a[ i ] - i，对 a’[ i ] 求最⻓不降⼦序列，可以得到最多有多少个位置保持不变；

如何改变，使前后数字变化量的绝对值的和最小？N<=35000，数据随机；

考虑dp：c[i]表示1-i的前缀修改的最小代价，显然我们要修改的是最长不降子序列相邻两数之间的位置，而最长不降子序列的转移不是唯一的，所以我们需要记录并枚举。如何求一段区间修改的代价呢？既然区间不能接上不降子序列，中间的数字一定小于a[L]或大于a[R]，而最终的修改结果是前一段全部改成a[L]，后一段全部改成a[R]；因为中间状态显然不是最优的；

单调队列维护凸包斜率优化DP

一个题能使用单调队列维护凸包，应该有以下几个条件：

1. 查询斜率单调。

2. 插入点的横坐标单调。

DP巧设状态

以中国象棋为例，询问NxM的棋盘，每行每列放置少于等于2个的棋子的方案数；

设 dp[i][j][k] 表示放了前i行，有j列是有1个棋子，有k列有2个棋子的方案数，转移一波即可；

进阶

询问NxM的棋盘，每行每列必须放置2个棋子的方案数；

此题当然可以用上面的思路O(n^3)来做，不过我们可以优化；设f[i][j]表示放了前i行，有j列放了2个棋子的方案数；由于前i行每行一定有2个，目前已经放置的棋子有2i个，那么放一个棋子的列就有2i-2j个，这样转移我们就可以压缩一维，答案为f[n][n]

再进阶

询问NxN的棋盘，每行每列必须放置2个棋子的方案数；

我们可以优化到O(n)，设f[i]表示i×i的方阵的方案数；

转移时这样讨论：

~~懒得写了~~

数位DP方法

为了免于数位DP最后的凑位步骤，在设计状态时可以加上一维，表示当前放置是否受限；

链接

树形DP注意环

RT，以P2515 [HAOI2010]软件安装为例，每个点均有一条出边，最后构成的图，可能是奇环树森林，由于依赖关系，一个环内的物品要么不选，要么都要选，所以需要Tarjan缩点；

Johnson 法则

可以概括为“双机器流水线问题”：有 n 个物品要由两台机器加工，每个物品都先在第一台机器上加工完成后再由第二台机器加工。第 i 个物品在两台机器上加工所需时间分别为 t1_x和 t2_x，求最优方案

设两项任务分别为 x,y，以 min(t1_x,t2_y)<min(t2_x,t1_y)为基准排序后即是最优方案；

基环树DP：骑士

在基环树森林中的没有上司的舞会；

处理的核心就在于处理环；考虑在环上的任意一点，它在最终答案中的情况只有两种：选/不选，每次强制规定一种状态，做一遍树形DP，取max；

注意图可能是森林；

划分数，求方案数

有n根木棍，第i根木棍的长度为Li，n根木棍依次连结了一起，总共有n-1个连接处。现在允许你最多砍断m个连接处，砍完后n根木棍被分成了很多段，要求满足总长度最大的一段长度最小，并且输出有多少种砍的方法使得总长度最大的一段长度最小。

~~一定不要把正解写挂了~~

第一问二分；第二问，注意到，朴素的dp，解的来源是后缀小于等于len的部分，前缀和优化即可；

求区间和的问题，最好直接转化为前缀和相减

预处理出最长后缀；

for(ri i = 1, c = 0; i <= n; ++i) {
        sum[i] = sum[i - 1] + w[i];
        while(sum[i] - sum[c] > len) ++c;
        lef[i] = c;
        s[i] = (s[i - 1] + (sum[i] <= len)) % md;
    }
    int ans = (sum[n] <= len);
    for(ri j = 2; j <= m + 1; ++j) {
        for(ri i = j; i <= n; ++i) {
            f[i] = (s[i - 1] - s[lef[i] - 1] + md) % md;
        }
        (ans += f[n]) %= md;
        s[0] = 0;
        for(ri i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + f[i];
        }
    }

变形的背包

有n种物品，每种物品有两套cost和val，每个物品必须选一套，求各个总cost下的最大/最小总val；

如何处理必须选？以最小值为例：

滚动数组，每次把待更新的数组设为inf，转移时，枚举两种转态，都使用上一个数组转移；

为什么？首先，两个状态，不是一个依赖另一个的dp数组转移过来的，所以两个转态是独立的（不会都选）；而初始dp数组为inf，要想转移，必须依靠上一个数组不为inf的位置，这就相当于每个物品，能选的话必须选；换句话说，取min不是和f[i-1]取（代表不选这个）而是和f[i]取；

区间DP

最好写循环，不写记忆化；

遇到特殊的情况：初值不方便设，答案不方便统计，怎么办？

刷表法：按照转移的顺序来；每一步都更新ans；

合并数列

有n个正整数，(2<=n<=262144)，范围在1-40。可以选相邻的两个相同的数，然后合并成一个比原来的大1的数（例如两个7合并成一个8)，目标是使得最大的数最大，请求最大值。

类似倍增的思想，非常有意思：

$f[i][j]=f[i-1][f[i-1][j]]$转移；关于最大的数，每2^i次方个数可以增加i，所以最大数为40+18； ## 超级麻将&&斗地主斗地主要DP出牌，懒得写了；超级麻将： $f[i][j][k][0/1]$表示“择第i号牌时，第i-1号牌选j张，第i号牌选k张，之前选的所有牌是否（0/1）选择了将（对子）”是否可行。它表示的其实是已经通过其他方法出完了j，k； 1.考虑选这i号牌做将（对子）： $if (k>1) f[i][j][k][1]|=f[i][j][k-2][0];

2.考虑i号牌碰（三张相同）：

if (k>=3) f[i][j][k][1]|=f[i][j][k-3][1],f[i][j][k][0]|=f[i][j][k-3][0];

3.考虑i号拍杠（四张相同）：

if (k>=4) f[i][j][k][1]|=f[i][j][k-4][1],f[i][j][k][0]|=f[i][j][k-4][0];

4.考虑i-2,i-1,i三张牌吃（三个连续数字）：

if (j>=k,a[i-2]>=k) f[i][j][k][0]|=f[i-1][a[i-2]-k][j-k][0],f[i][j][k][1]|=f[i-1][a[i-2]-k][j-k][1];

最后结果为f[100][a[99]][a[100]][1]。

如何满足“两人得分相同”的要求？

我们只要求相同，具体是多少不重要，所以我们直接记录两人得分之差即可；

刷表法会比填表法慢一些，也更可能RE？？？

拆分数列

给出一列数字，需要你添加任意多个逗号将其拆成若干个严格递增的数。如果有多组解，则输出使得最后一个数最小的同时，字典序最大的解（即先要满足最后一个数最小；如果有多组解，则使得第一个数尽量大；如果仍有多组解，则使得第二个数尽量大，依次类推……）。

首先要编写一个比较函数，忽略前导零；

设d[i]表示以i结尾的数列，最后一个数的最大下标，从前往后递推；

在得到d[n]之后，我们就固定了最后一个数

设f[i]表示后缀i中，第一个数字结束的最后位置；

输出方案时就从1开始不停的跳f；

注意 1234050 的最优方案是 12,34,050；

所以对于d[n]之前的前导零，要进行特判，f[zero]=n

P3084 [USACO13OPEN]照片Photo

农夫约翰决定给站在一条线上的N(1 <= N <= 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。

于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了编号a_i 到 b_i的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。

在拍完照片后，约翰发现了一个有趣的事情：每张照片中都有且仅有一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。

很神的DP；主要难点是不知道如何设置状态，因为要知道上一个放置的位置；

用f[i]f[i]表示到第i个位置为止且第i个位置必放，最多能放多少个

因为有两个限制条件：每个区间至少一个，每个区间至多一个

因为一个区间至多一个，所以所有包含这个点的区间都不能再放，要找到所有包含这个点的区间中最小的左端点，令r[i]=左端点-1（r[i]的初值均为i-1）

因为一个区间至少一个，所以不能有地方空着不放，找到整个区间在当前点之前的区间，取最大的左端点，令l[i]=左端点

每一次读入的时候，用x更新l[y+1]用x-1更新r[y]

然后正着扫一遍，用l[i-1]更新l[i]（在i-1之前的左端点必定在i之前）；然后倒着扫一遍，用r[i+1]更新r[i]（注意覆盖n+1）

所以f[i]=max\{f[j]+1,l[i]<=j<=r[i]\}，开个单调队列优化

把可行性DP转化为最优化DP，往往可以消掉⼀维

[APIO2015]巴厘岛的雕塑

给定⻓度为 N 的序列，和参数 A、B
• 把序列划分成 K(A <= K <= B)段，最⼩化每⼀段
的和的或
• Part1 : N <= 100
• Part2 : N <= 2000, A = 1

Part 1：

划分的段数有上下界，设f[i][j]表示把前i个数分成j段是否可行；

可行？什么是可行？

根据位运算的性质，我们往往都要按位考虑，每一位优先考虑填0，再考虑填1；

可行=这一位是0；

但是当我们确定了前几位的01后，对后面的分组是有限制的；

具体来说，之前已经确定填0的位，我们在后面分组的时候就不能填1；

也就是

if((((s[i] - s[k - 1]) >> w) & 1) == 0 && ((((s[i] - s[k - 1]) >> (w + 1)) << (w + 1)) | ans) == ans)
    f[i][j] |= f[k - 1][j - 1];

这一段的和这一位是0，且之前ans是0的都是0；

对于Part 2：

我们只有了分组的上线：考虑如果没有分组的任何限制，我们一定是把每个数分成一组，而有了限制，我们就想尽可能多的分组；设g[i]表示前i个数分成一组，使这一位为0，最少的分组数量；

我们就优化掉一维了；

DP优化状态，可以尝试交换维度，或把目标量当作已知量作为一维

bzoj3090：
有 N 个农民, 他们住在 N 个不同的村子里. 这 N 个村子形成一棵树.
每个农民初始时获得 X 的钱.
每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民.
对于每个农民给定一个值 v_i, 求最少需要多少次操作, 使得每个农民最终拿到的钱 >= 给定的值.

容易想到一种DP：f[i][j]表示i的子树，能向外贡献/需要得到j元的最少交换次数；

但是钱数很大，时空不允许？？？

交换状态，考虑到交换次数是N级别的；

对每个点 x 依次考虑它的每个孩子，对于一条父子边 (x,y)，有：这条边加入图中 $f[x][i]+f[y][j]→f'[x][i+j+1]

如果 f[y][j]≥0，那么可以不要这条边，让树从这里断开：f[x][i]→f'[x][i+j]

在实现转移方程时，要注意观察决策集合的范围随着状态的变化情况，对于“决策集合中的元素只增多不减少”的情景，可以维护一个变量记录当前决策集合的信息，避免重复扫描

有时可以通过额外的算法确定DP状态的顺序，有时可以在状态空间中运用等效的手法对状态进行缩放

以cookies为例：

圣诞老人共有M个饼干，准备全部分给N个孩子。每个孩子有一个贪婪度，第 i 个孩子的贪婪度为 g[i]。
如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多，那么第 i 个孩子会产生 g[i]*a[i]的怨气。
给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。
1≤N≤30, N≤M≤5000, 1<=gi<=10^7。

一个孩子的怒气大小与其他孩子获得的饼数有关，很难产生子结构；

思考可以发现，贪婪度大的孩子应该获得更多的饼干，因此把N个孩子按照贪婪度从大到小排序，他们分得的饼干数量将是递减的；

设f[i][j]表示前i个孩子获得j块饼干时的最小怒气值，但在转移时发现，我们还需要知道第i个孩子获得的饼干数，和i前面有多少个孩子和i相同，这样状态太大了；

等价转换：

1.若第i个孩子获得的饼干数大于1，则等价于分配j-i个饼干给前i个孩子，每人少拿一块饼干，相对大小不变；

2.若第i个孩子获得的饼干数量为1，枚举i前面有多少孩子也获得1块饼干；

数位DP

在设计状态时，最好不要设为：后面的位要满足...状态；而是设为，前面的位已经满足了...状态，后面的位全部满足状态的方案数；