Hobo Chen

ACM-动态规划(TBD)

这篇博客包含了一些常见动态规划算法/题目。

概述

对于动态规划,需要思考的是:

  1. 状态是什么
  2. 状态之间怎么转移

01背包DP

NOIP 2005采药

给定背包容量T,给出M个物品,分别有体积V_i和价值W_i。

最最简单的DP题了。

dp[i][j]代表在剩余i的容量下当前决策到j物品所能获得的最大收益,可以对j使用滚动数组;复杂度$O(MT)$。

数位DP

UESTC250

定义任何不含前导0且相邻两个数组只差至少为2的正整数为windy书,

询问区间[l, r]内共有多少个windy数。

TODO

区间DP

区间DP是线性DP的一种。

[HDU 5115]

树DP

POJ 2342

给出一个树,每个点有权;选择某些点,要求点和点的父亲不能同时选;问权最大和。

非常简单的一个树DP,dp[i][0]代表i节点没有被选情况下的最大权;dp[i][1]代表i节点被选了的最大权。

DFS做一遍即可。

DAG DP

DAG为有向无环图,对于其之上的最长路径/最短路径/路径计数等统称为DAG DP。

最长路径

HDU1069

给若干个长方体,问堆的最高高度。上面一块的底面必须完全在下面一块上表面内。

记f[i]为到i的最长路径;记忆化搜索即可。

字符串DP

POJ3267

给出一个字符串(长度小于400)和一个字典,要求删除最少的字符数使字符串可被字典内某些单词拼接而成。

字符串的下标为[0,l−1]。记dp[i]为[i,l−1]内最少被删除的字符数。

无条件转移,dp[i]=dp[i+1]+1

有条件转移,当i−m内存在某个单词的时候,dp[i]=dp[m]+m−i+len,len为这个单词的长度。

其他

NOI2009 管道取珠

有上下两个管道,管道内有黑/白两种颜色的小球(分别不超过500个);每次操作为从 上/下 管道内取出第一个珠子;记ai为某种结果的不同操作序列数,求 $\sum a_i^2$。

题解:

首先可以证明 $a^2_i$ 为某种结果的操作序列的有序对数目。

f[i1][j1][i2][j2]表示操作序列X的状态为i1,j1,操作序列Y的状态为i2,j2,且X,Y的当前输出序列相同的有序操作序列对数量。其中i,j表示为,上管道取了i个小球,下管道取了j个小球。

同时有i1+j1=i2+j2,时间和空间复杂度均可优化至$O(n^3)$。

CF590 D

题意:

给出N(<=150)个数,每次操作为交换相邻两个数,要求在$S, S<10^9$个操作内使前K个数的和最小。

题解:

先特判S是否可以将所有数交换,如果可以则排序输出。

问题可以等价转换为在一个下标为1−N的数列内,取K项,满足下标和不超过 $ S+K∗(K+1)^{2}$ 的情况下,使和最小。

f[i][j][k]表示在前i项内,已经取了j个数,其下标和为k的最小值。

需要对i使用滚动数组优化空间。