提高级-动态规划-动态规划的常用优化

# 动态规划的常用优化

动态规划的优化主要根据所研究的问题性质，对空间复杂度和时间复杂度进行优化。

---
## 滚动数组优化

滚动数组是DP中的一种编程思想。简单的理解就是让数组滚动起来，每次都使用固定的几个存储空间，来达到压缩，节省存储空间的作用。起到优化空间，主要应用在递推或动态规划中（如01背包问题）。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。

当然是用时间去换空间的

---

举个简单的例子

斐波那契数列：

```cpp
#include<stdio.h>

int main()

{

int i;

long long d[80];

d[0]=1;

d[1]=1;

for(i=2;i<80;i++)

{

d[i]=d[i-1]+d[i-2];

}

printf("%lld\n",d[79]);

return 0;

}
```

---

上面这个循环d\[i\]只依赖于前两个数据d\[i - 1\]和d\[i - 2\]; 为了节约空间用滚动数组的做法。

```cpp
#include<stdio.h>

int main()

{

int i;

long long d[3];

d[1]=1;

d[2]=1;

for(i=2;i<80;i++)

{

d[0]=d[1];

d[1]=d[2];

d[2]=d[0]+d[1];

}

printf("%lld\n",d[2]);

return 0;

}
```

---

另一种表达形式

```cpp
#include<stdio.h>

int main()

{

int i;

long long d[3];

d[0] = 1;

d[1] = 1;

for(i=2;i<80;i++)

{

d[i%3]=d[(i-1)%3]+d[(i-2)%3];

}

printf("%lld\n",d[79%3]);

return 0;

}
```

---

### 二维数组举例

```
int i, j, d[100][100];
for(i = 1; i < 100; i++)
    for(j = 0; j < 100; j++)
        d[i][j] = d[i - 1][j] + d[i][j - 1];`
```
上面的d\[i\]\[j\]只依赖于d\[i - 1\]\[j\], d\[i\]\[j - 1\];

运用滚动数组

```
int i, j, d[2][100];
for(i = 1; i < 100; i++)
    for(j = 0; j < 100; j++)
        d[i % 2][j] = d[(i - 1) % 2][j] + d[i % 2][j - 1];
```
---
## 单调队列/单调栈优化

例题一[「一本通 5.5 练习 1」烽火传递](http://39.99.183.126:8888/p/YBTS1602)

例题二[P2034 选择数字](https://www.luogu.com.cn/problem/P2034)

---

例题 [CF372C Watching Fireworks is Fun](http://codeforces.com/problemset/problem/372/C)

题目大意：城镇中有 $n$ 个位置，有 $m$ 个烟花要放。第 $i$ 个烟花放出的时间记为 $t_i$，放出的位置记为 $a_i$。如果烟花放出的时候，你处在位置 $x$，那么你将收获 $b_i-|a_i-x|$ 点快乐值。
    
初始你可在任意位置，你每个单位时间可以移动不大于 $d$ 个单位距离。现在你需要最大化你能获得的快乐值。

---

设 $f_{i,j}$ 表示在放第 $i$ 个烟花时，你的位置在 $j$ 所能获得的最大快乐值。

写出 **状态转移方程**：$f_{i,j}=\max\\{f_{i-1,k}+b_i-|a_i-j|\\}$

这里的 $k$ 是有范围的，$j-(t_{i}-t_{i-1})\times d\le k\le j+(t_{i}-t_{i-1})\times d$。

---

我们尝试将状态转移方程进行变形：

由于 $\max$ 里出现了一个确定的常量 $b_i$，我们可以将它提到外面去。

$f_{i,j}=\max\\{f_{i-1,k}+b_i-|a_i-j|\\}=\max\\{f_{i-1,k}-|a_i-j|\\}+b_i$

如果确定了 $i$ 和 $j$ 的值，那么 $|a_i-j|$ 的值也是确定的，也可以将这一部分提到外面去。

最后，式子变成了这个样子：$f_{i,j}=\max\\{f_{i-1,k}-|a_i-j|\\}+b_i=\max\\{f_{i-1,k}\\}-|a_i-j|+b_i$

看到这一熟悉的形式，我们想到了什么？**单调队列优化**。由于最终式子中的 $\max$ 只和上一状态中连续的一段的最大值有关，所以我们在计算一个新的 $i$ 的状态值时候只需将原来的 $f_{i-1}$ 构造成一个单调队列，并维护单调队列，使得其能在均摊 $O(1)$ 的时间复杂度内计算出 $\max\\{f_{i-1,k}\\}$ 的值，从而根据公式计算出 $f_{i,j}$ 的值。

总的时间复杂度为 $O(nm)$。

---

### 参考代码
```cpp
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;

const int maxn = 150000 + 10;
const int maxm = 300 + 10;

ll f[2][maxn];
ll a[maxm], b[maxm], t[maxm];
int n, m, d;

int que[maxn];

int fl = 1;

void init() {
  memset(f, 207, sizeof(f));
  memset(que, 0, sizeof(que));
  for (int i = 1; i <= n; i++) f[0][i] = 0;
  fl = 1;
}

void dp() {
  init();
  for (int i = 1; i <= m; i++) {
    int l = 1, r = 0, k = 1;
    for (int j = 1; j <= n;
         j++) {  // 在这里使用了单调队列的优化，推式子详见上面
      for (; k <= min(1ll * n, j + d * (t[i] - t[i - 1])); k++) {
        while (l <= r && f[fl ^ 1][que[r]] <= f[fl ^ 1][k]) r--;
        que[++r] = k;
      }

while (l <= r && que[l] < max(1ll, j - d * (t[i] - t[i - 1]))) l++;
      f[fl][j] = f[fl ^ 1][que[l]] - abs(a[i] - j) + b[i];
    }

fl ^= 1;
  }
}

int main() {
  cin >> n >> m >> d;
  for (int i = 1; i <= m; i++) cin >> a[i] >> b[i] >> t[i];

// then dp
  dp();
  ll ans = -1e18;
  for (int i = 1; i <= n; i++) ans = max(ans, f[fl ^ 1][i]);
  cout << ans << endl;
  return 0;
}
```

---

讲完了，让我们归纳一下单调队列优化动态规划问题的基本形态：当前状态的所有值可以从上一个状态的某个连续的段的值得到，要对这个连续的段进行 RMQ 操作，相邻状态的段的左右区间满足非降的关系。

---

## 单调队列优化多重背包

问题描述

你有 $n$ 个物品，每个物品重量为 $w_i$，价值为 $v_i$，数量为 $k_i$。你有一个承重上限为 $W$ 的背包，现在要求你在不超过重量上限的情况下选取价值和尽可能大的物品放入背包。求最大价值。

设 $f_{i,j}$ 表示前 $i$ 个物品装入承重为 $j$ 的背包的最大价值，朴素的转移方程为

$$
f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\times w_i}+v_i\times k)
$$

时间复杂度 $O(W\sum k_i)$。

---

考虑优化 $f_i$ 的转移。为方便表述，设 $g_\{x,y\}=f_\{i,x \times w_i+y\},g'_\{x,y\}=f_\{i-1,x\times w_i+y\}$，其中 $0 \le y \lt w_i$，则转移方程可以表示为：

$$
g_{x,y}=\max_{k=0}^{k_i}(g'_{x-k,y}+v_i\times k)
$$

设 $G_{x,y}=g'_{x,y}-v_i\times x$。则方程可以表示为：

$$
g_{x,y}=\max_{k=0}^{k_i}(G_{x-k,y})+v_i\times x
$$

---

这样就转化为一个经典的单调队列优化形式了。$G_{x,y}$ 可以 $O(1)$ 计算，因此对于固定的 $y$，我们可以在 $O\left( \left\lfloor \dfrac{W}{w_i} \right\rfloor \right)$ 的时间内计算出 $g_{x,y}$。因此求出所有 $g_{x,y}$ 的复杂度为 $O\left( \left\lfloor \dfrac{W}{w_i} \right\rfloor \right)\times O(w_i)=O(W)$。这样转移的总复杂度就降为 $O(nW)$。

在实现的时候，我们需要先枚举 $y$，这样才能保证枚举 $x$ 的时候利用单调队列进行优化，而单调队列中存储的是 $x-k$，并不存储 $k$，这样使用的时候需要通过 `f[last][q.front() * w[i] + y] - q.front() * v[i]` 获取对应的 $G_{x-k,y}$，不难发现 $x-k\in [x - k_i,x]$，因此在枚举 $x$ 的时候，我们需要删除队列中不在这个范围内的元素。

---

### 参考代码
```cpp
#include <bits/stdc++.h>

constexpr int MAXV = 4e4 + 10;
constexpr int MAXN = 1e2 + 10;

using namespace std;

int n, W, last = 0, now = 1;
array<int, MAXN> v, w, k;
array<array<int, MAXV>, 2> f;
deque<int> q;

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> W;
  for (int i = 1; i <= n; i++) {
    cin >> v[i] >> w[i] >> k[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int y = 0; y < w[i]; y++) {
      // 清空队列
      deque<int>().swap(q);
      for (int x = 0; x * w[i] + y <= W; x++) {
        // 弹出不在范围的元素
        while (!q.empty() && q.front() < x - k[i]) {
          q.pop_front();
        }
        // 保证队列单调
        while (!q.empty() && f[last][q.back() * w[i] + y] - q.back() * v[i] <
                                 f[last][x * w[i] + y] - x * v[i]) {
          q.pop_back();
        }
        q.push_back(x);
        f[now][x * w[i] + y] =
            f[last][q.front() * w[i] + y] - q.front() * v[i] + x * v[i];
      }
    }
    swap(last, now);
  }
  cout << f[last][W] << endl;
  return 0;
}
```

---

## 习题
-  [NOIPS2012C. 开车旅行](http://39.99.183.126:8888/p/NOIPS2012C)
-  [NOI2011E NOI 嘉年华](http://39.99.183.126:8888/p/NOI2011E)
-  [NOI2013E 书法家](http://39.99.183.126:8888/p/NOI2013E)
-  [NOIPS2012C. 开车旅行](http://39.99.183.126:8888/p/NOIPS2012C)
-  [NOIP2017 普及组 跳房子](http://39.99.183.126:8888/p/NOIPJ2017D)
-  [NOIPJ2018C. 摆渡车](http://39.99.183.126:8888/p/NOIPJ2018C)
-  [CSPS2019D  Emiya 家今天的饭](http://39.99.183.126:8888/p/CSPS2019D)
-  [CSPS2019E  划分](http://39.99.183.126:8888/p/CSPS2019E)
-  [POI2011 TEM-Temperature](http://39.99.183.126:8888/p/4150)
-  [POI2014 PTA-Little Bird](http://39.99.183.126:8888/p/4153)
-  [APIO2020 粉刷墙壁](http://39.99.183.126:8888/p/APIO2020A)
-   [「Luogu P1886」滑动窗口](https://loj.ac/problem/10175)
-   [「NOI2005」瑰丽华尔兹](https://www.luogu.com.cn/problem/P2254)
-   [「SCOI2010」股票交易](https://loj.ac/problem/10183)