DP的花式优化方法
本文章可能不会继续更新，可以在单独的题解里面找找有没有有趣的DP题目。
这里不分类介绍具体的优化方法，而是收集一些比较有意思的题目，从题目出发讲优化。
一些优化手段：
[NOI2005]瑰丽华尔兹：从4次方到3次方
朴素的想法
这个题是一个DP问题，设计状态为dp[i, j, k]为在(i, j)处，k时间段末的滑行最长距离。考虑从上一时间段转移过来，如果不考虑障碍物，假设在第一坐标上移动，转移方程应该如下：
dp[i, j, k] = \max \{dp[i', j, k - 1] + i - i'\} \ (i - i' \leq t)
对于每一个时间段k，对于每一个点(i, j)进行时间段方向上的转移，单次转移遍历该方向的点，复杂度为1次。遍历地图的复杂度为2次，遍历时间段的复杂度为1次，总和即为4次。
对于200的数据，4次显然是不够的，考虑优化这一过程。
降低时间：单调队列
我们发现这个题可以维护区间上长度为t的一段 dp[i', j, k - 1] - i' 的最大值，这个过程可以用单调队列降掉1次。3次的复杂度是可以接受的。
降低空间：滚动数组
注意到转移只跟上一层即k-1有关系，这就可以对这一维进行滚动。空间减少1次。滚动数组对cache友好，还能优化下常数。
降低空间：降维
转移具有一定的方向性，如果按照一定顺序转移可以达到更新而不发生错误的效果。经过分析后，k这一维可以删去。
说了这么多，没代码说个**
那就给你们代码嘛。
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <algorithm>
const int NINF = 0xc0c0c0c0;
const int fix[5][5] = {{0, -1, 1, 0, 0}, {0, 0, 0, -1, 1}};
int n, m, x, y, k, dp[205][205], si, ti, di, que[205], pos[205], l, r, v, now, ans = -1;
char mmp[205][205];
inline void workdp(int nx, int ny, int d, int t) {
l = r = 1;
now = 1;
while(nx <= n && ny <= m && nx >= 1 && ny >= 1) {
if(mmp[nx][ny] == 'x') {
l = r = 1;
}
v = dp[nx][ny] - now;
if(v >= NINF) {
while(l < r && que[r - 1] <= v) r--;
que[r] = v;
pos[r] = now;
r++;
}
while(l < r && now - pos[l] > t) l++;
if(l < r) {
dp[nx][ny] = que[l] + now;
} else {
dp[nx][ny] = NINF;
}
ans = std::max(ans, dp[nx][ny]);
nx += fix[0][d];
ny += fix[1][d];
now++;
}
}
int main() {
scanf("%d%d%d%d%d", &n, &m, &x, &y, &k);
for(int i = 1; i <= n; i++) {
scanf("%s", mmp[i] + 1);
}
memset(dp, 0xc0, sizeof dp);
dp[x][y] = 0;
while(k--) {
scanf("%d%d%d", &si, &ti, &di);
if(di == 1) {
for(int i = 1; i <= m; i++) workdp(n, i, di, ti - si + 1);
}
if(di == 2) {
for(int i = 1; i <= m; i++) workdp(1, i, di, ti - si + 1);
}
if(di == 3) {
for(int i = 1; i <= n; i++) workdp(i, m, di, ti - si + 1);
}
if(di == 4) {
for(int i = 1; i <= n; i++) workdp(i, 1, di, ti - si + 1);
}
}
printf("%d", ans);
return 0;
}
宝物筛选_NOI导刊2010提高（02）：多重背包的二进制优化和单调队列优化
多重背包的二进制优化
说明
如果将一个数字拆成1, 2, 4, 8, \cdots , 2^n, n - 2^n这些数字，可以证明这些数字可以组合成1~n的任意一个数字，对每个物品的数量如此拆分，即可转换为01背包问题。这样的复杂度是O(V * \sum (\log n_i))的。
代码
// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0, neg = 1;
while(*s < '0' || *s > '9') if(*(s++) == '-') neg = -1;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res * neg;
}
} ip;
#define read ip.read
int n, w, val, wei, num, dp[40005], j;
int main() {
n = read();
w = read();
for(int i = 1; i <= n; i++) {
val = read();
wei = read();
num = read();
for(j = 0; (1 << (j + 1)) - 1 <= num; j++) {
for(int k = w; k >= wei * (1 << j); k--) {
dp[k] = std::max(dp[k], dp[k - wei * (1 << j)] + val * (1 << j));
}
}
if((1 << j) - 1 < num) {
j = num - ((1 << j) - 1);
for(int k = w; k >= wei * j; k--) {
dp[k] = std::max(dp[k], dp[k - wei * j] + val * j);
}
}
}
printf("%d", dp[w]);
return 0;
}
多重背包的单调队列优化
说明
回到最原始的转移方程：
dp[i][j] = \max \{dp[i - 1][j - k * c_i] + k * v_i\} \ (0 \leq k \leq \min (n_i, \lfloor \frac{j}{c_i} \rfloor))
这里的转移，一定是从比j小c_i整数倍的位置转移而来。我们可以讨论j模c_i的值，对一个剩余类内部进行单调队列的转移。从 (j \mod c_i) + k * c_i 这个状态往 (j \mod c_i) + k' * c_i \ (k' \geq k) 这个状态转移。这样做复杂度可以减为 O(V * N) 。
当然你还可以对i维度进行滚动数组优化空间。
代码
// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0, neg = 1;
while(*s < '0' || *s > '9') if(*(s++) == '-') neg = -1;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res * neg;
}
} ip;
#define read ip.read
inline int g(int i) {
return i & 1;
}
int n, w, val, wei, num, que[40005], pos[40005], l, r, dlt, v, dp[2][40005];
int main() {
n = read();
w = read();
for(int i = 1; i <= n; i++) {
val = read();
wei = read();
num = read();
for(int j = 0; j < wei; j++) {
l = r = 1;
dlt = 0;
for(int k = 0; j + k * wei <= w; k++) {
v = dp[g(i - 1)][j + k * wei] - dlt;
while(l < r && que[r - 1] <= v) r--;
que[r] = v;
pos[r] = k;
r++;
while(l < r && k - pos[l] > num) l++;
dp[g(i)][j + k * wei] = std::max(dp[g(i)][j + k * wei], que[l] + dlt);
dlt += val;
}
}
}
printf("%d", dp[g(n)][w]);
return 0;
}
