[算法汇总]线性dp
Nickel_Angel
2019-06-17 21:32:21
这里是线性dp的例题剖析$QwQ$~~
[P1020 导弹拦截](https://www.luogu.org/problemnew/show/P1020)
本题为二维偏序（时间为第一维，高度为第二维，而数据保证第一维有序，所以不用排序）:
第一问，直接对时间求最长不下降序列长度即可……
第二问，则是求严格上升的最长序列长度……
下面是对于给定序列求其最长单调上升子序列的长度的代码……
Code：
(下文中n为序列长度， a为序列)
$O(n^2)$的算法：
```cpp
int LIS(int *a, int n)
{
int dp[n];
//这里dp数组的意义为：以第i个数结尾的最长不下降序列长度
for (int i = 1; i <= n; ++i)
{
dp[i] = 1;//初始化
for (int j = 1; j < i; ++j)
{
if (dp[j] < dp[i])
dp[i] = max(dp[i], dp[j] + 1);
//如果能继承且继承更优，则更新状态
}
}
return dp[n];
}
```
$O(n\log{n})$的算法：
```cpp
int LIS(int *a, int n)
{
int dp[n];
//这里dp数组的意义为：该序列中，上升子序列长度为i的上升子序列的最小末尾数值，运用了贪心的思想
memset(dp, 0x3f, sizeof(dp));//初始化为无限大
dp[1] = a[1];
int res = 1, s, e, mid;
for (int i = 2; i <= n; ++i)
{
s = 0, e = res;
if (a[i] > dp[res]) dp[++res] = a[i];//如果能继承更新状态
else
{
//二分找第一个dp数组中大于当前a[i]中的数值
while (s < e)
{
mid = (s + e) >> 1;
if (dp[mid] > a[i]) e = mid;
else s = mid + 1;
}
dp[s] = min(dp[s], a[i]);
}
}
return res;
}
```
又如 [P1091 合唱队形](https://www.luogu.org/problemnew/show/P1091)
求一个序列中前半段严格递增后半段严格递减的子序列长度的最大值$len_{max}$后
$n - len_{max}$即为所求。
考虑对序列正向求一遍最长上升再反向求一遍最长上升枚举断点找最大即可。
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int h[105], f[105], g[105], n, ans = 0;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", h + i);
for (int i = 1; i <= n; ++i)
{
f[i] = 1;
for (int j = 0; j < i; ++j)
{
if (h[j] < h[i])
f[i] = max(f[i], f[j] + 1);
}
}
for (int i = n; i > 0; --i)
{
g[i] = 1;
for (int j = n + 1; j > i; --j)//注意从n+1开始
{
if (h[j] < h[i])
g[i] = max(g[i], g[j] + 1);
}
}
for (int i = 1; i <= n; ++i) ans = max(ans, f[i] + g[i] - 1);
printf("%d", n - ans);
return 0;
}
```
[P5414 [YNOI2019]排序](https://www.luogu.org/problemnew/show/P5414)
本题从本质上讲是询问对于给定序列，每次可对序列中的数字进行移动，每次移动的代价是这个数字本身，求出使序列成为单调上升序列的最小代价……
我们发现要得到最小代价，由于加入我们需调整序列中某个数$a_k$在序列中的位置，我们既可以选择直接移动，也可以选择移动序列中的不包含$a_k$的一段数，故为达到最优，每个数至多移动一次……
发现如果将一个数**移动**到了它该放的位置，那么这个数以后对答案就无贡献了……故这个数可以视为被删去……
不难发现，我们只需求出如何在序列中删去一些数，使序列成为单调上升序列，并使删去数之和最小……
既然删去的和最小，那么留下的数之和就最大，即在序列中求一个递增的子序列，使其和最大（形如这样问题被称为**递增子序列最大和**问题）……
最后用整个序列的和减去递增子序列最大和即为答案。
下文是使用dp求解递增子序列最大和的方法：（设序列为$\{a_n\}$）
定义$dp[i]$为以$a_i$为最后一个数的递增子序列最大和
故有：
初始：$dp[i] = a[i],i \in [1,n]$；
转移：$dp[i] = max(dp[j]) + a[i] \text{ 其中 $1 \leq j < i \leq n$ 且 $a[j] < a[i]$}$；
答案：$ans = max(dp[i]),i \in [1,n]$。
本题Code：
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int T, n, v[105], dp[105], sum, maxsum;
int main()
{
scanf("%d", &T);
while (T--)
{
sum = 0, maxsum = 0;
memset(dp, 0, sizeof(dp));
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", v + i);
sum += v[i];//sum统计前缀和
}
for (int i = 1; i <= n; ++i)
{
dp[i] = v[i];//注意dp数组初始化
for (int j = 1; j < i; ++j)
{
if (v[j] <= v[i])
dp[i] = max(dp[i], dp[j] + v[i]);
}
maxsum = max(maxsum, dp[i]);//maxsum记录递增子序列最大和
}
printf("%d\n", sum - maxsum);//两sum相减即为答案
}
return 0;
}
```
[P1115 最大子段和](https://www.luogu.org/problemnew/show/P1115)
简单的题目描述：给出一段序列，选出其中连续且非空的一段使得这段和最大。
本题dp需要计算两个数组：（仍设序列为$\{a_n\}$）
$f[i]$：表示由$a_{1 \cdots i}$的子序列所构成的最大子段和
$g[i]$：表示由$a_{1 \cdots i}$的子序列所构成的且选入最大子段和的最后一个数为$a_i$的最大子段和
故有：
初始：$f[0] = -\infty$
转移：
$g[i] = max(g[i - 1] + a[i], a[i])$；
$f[i] = max(f[i - 1], g[i])$；
答案：$f[n]$
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200001;
int n, f[maxn], g[maxn], x;
int main()
{
scanf("%d", &n);
f[0] = -INT_MAX;
for (int i = 1; i <= n; ++i)
{
scanf("%d", &x);
g[i] = max(g[i - 1] + x, x);
f[i] = max(f[i - 1], g[i]);
}
printf("%d", f[n]);
return 0;
}
```
[P1280 尼克的任务](https://www.luogu.org/problemnew/show/P1280)
由于当前时刻的最大空闲时间是和后面选择任务的持续时间的时刻有关系的，所以需要倒着推……
令$dp[i]$表明从$n$到$n-i+1$时刻的最大空闲时间，所以：
$$ dp[i] = \begin{cases} dp[i + 1] + 1 & \text {如果$i$时刻无任务} \\ max(dp[i], dp[i + t[j]]) & \text {如果$i$时刻有任务，其中$j \in task(i)$}\end{cases} $$
其中$task(i)$为在$i$时刻开始的任务编号集合，$t[j]$ 为任务编号为$j$的任务的持续时间。
$dp[1]$即为答案。
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 10010;
int n, k, dp[maxn];
vector<int> task[maxn];//这里用vector记录了t[i]
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1, s, t; i <= k; ++i)
{
scanf("%d%d", &s, &t);
task[s].push_back(t);
}
for (int i = n; i > 0; --i)
{
if (task[i].size() == 0) dp[i] = dp[i + 1] + 1;
else
{
for (int j = 0; j < (int)task[i].size(); ++j)
{
dp[i] = max(dp[i], dp[i + task[i][j]]);
}
}
}
printf("%d", dp[1]);
return 0;
}
```
[P1541 乌龟棋](https://www.luogu.org/problemnew/show/P1541)
由于只有四种卡牌，每种卡牌的总数不超过40，所以可以考虑将目前使用四种卡牌的数量设计进状态……
我们又惊奇的发现只要知道了四种卡牌的数量，就可以算出当前所到达的格子，进而算出当前的得分。
在这里，我们定义第$i$种卡牌的总量为$card_i$，$a[i]$的意义如题所述，$dp[i][j][k][l]$的意义为：在用了$i$张1卡牌，$j$张2卡牌，$k$张3卡牌，$l$张4卡牌的方案数。
故状态转移方程为：
$$dp[i][j][k][l] = max(dp[i-1][j][k][l], dp[i][j-1][k][l],dp[i][j][k-1][l],dp[i][j][k][l-1]) + a[pos]$$
其中$pos = 1+i+j \times 2+k \times 3 + l \times 4$，即使用当前的卡牌走到的格子是第几个。
边界：$dp[0][0][0][0] = a[1]$，（显然，起点为第一个格子，未开始走时直接获得$a[1]$的分数）
答案即为：$dp[card_1][card_2][card_3][card_4]$
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename T>
inline bool chkmax(T &x, const T &y) {return x < y ? (x = y, true) : false;}
int n, m, a[360], card[5], dp[41][41][41][41];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
for (int i = 1, x; i <= m; ++i)
{
scanf("%d", &x);
++card[x];
}
dp[0][0][0][0] = a[1];
int pos;
for (int i = 0; i <= card[1]; ++i)
{
for (int j = 0; j <= card[2]; ++j)
{
for (int k = 0; k <= card[3]; ++k)
{
for (int l = 0; l <= card[4]; ++l)
{
pos = 1 + i + 2 * j + 3 * k + 4 * l;
//注意数组越界问题,即当某变量在其值为0时特判,否则会出现数组下标为负数的情况
if (i != 0)
chkmax(dp[i][j][k][l], dp[i - 1][j][k][l] + a[pos]);
if (j != 0)
chkmax(dp[i][j][k][l], dp[i][j - 1][k][l] + a[pos]);
if (k != 0)
chkmax(dp[i][j][k][l], dp[i][j][k - 1][l] + a[pos]);
if (l != 0)
chkmax(dp[i][j][k][l], dp[i][j][k][l - 1] + a[pos]);
}
}
}
}
printf("%d", dp[card[1]][card[2]][card[3]][card[4]]);
return 0;
}
```
[P1156 垃圾陷阱](https://www.luogu.org/problemnew/show/P1156)
本题的动态规划不是用来直接计算答案的 ~~要不然我为什么怎么推式子也推不出来QAQ~~
发现只要模拟并判断奶牛是否能活到垃圾的总高$h_{total}$增加到$D$英尺就能得到答案，我们可以考虑用$dp[i][j]$记录在第$i$个垃圾投入时，目前垃圾已堆了$j$英尺高的最大体力值。
在这里，我们用$trash[i].t,trash[i].f,trash[i].h$分别表示第$i$个垃圾的被投进井中的时间，该垃圾能维持奶牛生命的时间和该垃圾能垫高的高度。
不难发现，当有垃圾投入时，奶牛可以选择吃掉它补充体力或不吃它使垃圾总高度增加，故：
只有当$dp[i][j] \geq 0$（即当前奶牛未死亡）且$dp[i][j] - trash[i + 1].t + trash[i].t \geq 0$（即奶牛能支撑到下一个垃圾投入）时，才可转移，否则奶牛会~~当场去世~~（这里，如果奶牛不能活着达到$dp[i][j]$的相应状态，我们令其值为-1，以区分当奶牛达到$dp[i][j]$的相应状态时，体力值恰好为0，即濒死的情况）
转移时就考虑这两种决策即可：
$$\begin{cases} dp[i + 1][j + trash[i + 1].h] = dp[i][j] - trash[i + 1].t + trash[i].t & \text{选择加高度} \\ dp[i+1][j] = max(dp[i + 1][j], dp[i][j] - trash[i+1].t + trash[i].t + trash[i + 1].f) & \text{选择补体力} \end{cases}$$
边模拟，边计算$dp[i][j]$的值，如果$j + trash[i + 1].h \geq D$且$dp[i][j] \geq trash[i + 1].t - trash[i].t$那么奶牛便可在下个垃圾投放时跳出陷阱；
如果到第$n$个垃圾投放完毕都不能满足的话，由于不能成功跳出，需求奶牛最长可以存活多长时间，我们可以重新模拟，只需看当奶牛在活着的情况下，选择将所有投放的垃圾吃掉的存活时间即可。
大体思路考虑完后，考虑细节问题，我们发现我们的状态转移在时间上分先后，故应将所有投放的垃圾，按时间从先至后的顺序排序；由于一开始奶牛有10的体力值，故$dp[0][0] = 10$
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename T>
inline bool chkmax(T &x, const T &y) {return x < y ? (x = y, true) : false;}
int d, n;
int dp[101][1100], maxt = 10, sumt = 0, maxh[4010], maxf[210];
struct trash
{
int t, f, h;
}obj[101];
bool cmp(trash x, trash y) {return x.t < y.t;}
int main()
{
memset(dp, -1, sizeof(dp));
scanf("%d%d", &d, &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d%d", &obj[i].t, &obj[i].f, &obj[i].h);
sort(obj + 1, obj + n + 1, cmp);
dp[0][0] = 10, obj[0].f = obj[0].t = obj[0].h = 0;
//由于状态转移是依靠dp[i][j]来更新dp[i+1][j],故一定要有"0号垃圾"作为初始状态
for (int i = 0; i < n; ++i)
{
for (int j = 0; j <= d; ++j)
{
if (dp[i][j] < 0) continue;
if (j + obj[i + 1].h >= d && dp[i][j] >= obj[i + 1].t - obj[i].t)
{
printf("%d", obj[i + 1].t);
return 0;
}
if (dp[i][j] - obj[i + 1].t + obj[i].t >= 0)
{
dp[i + 1][j + obj[i + 1].h] =
dp[i][j] - obj[i + 1].t + obj[i].t;
chkmax(dp[i + 1][j],
dp[i][j] - obj[i + 1].t + obj[i].t + obj[i + 1].f);
}
}
}
int sum = 0, remain = 10;//不能成功跳出,选择将所有投放的垃圾吃掉,重新模拟
for (int i = 1; i <= n; ++i)
{
if (obj[i].t - obj[i - 1].t > remain)
{
printf("%d", sum + remain);
return 0;
}
sum += obj[i].t - obj[i - 1].t;
remain -= obj[i].t - obj[i - 1].t;
remain += obj[i].f;
}
printf("%d", sum + remain);
return 0;
}
```
[P1052 过河](https://www.luogu.org/problemnew/show/P1052)
~~如果你足够聪明~~，应该立刻想出本题依靠$L$的范围的状态转移方程$\cdots$~~我没想出来，自闭了QAQ~~
即：
$$dp[i] = min(dp[i - j]) + add[i]\text{ 其中 $S \leq j \leq T$，$add[i]$ = [$i$处有石子]}$$
这样转移为$O(L)$的时间，但$L \leq 1 \times 10^9$，会TLE
发现石头个数很少，看看有什么特殊性质：
~~由于自己没看懂证明，先上结论~~ 设每次走$p$或$p+1$步，如果两个石子之间距离大于$p \times (p + 1)$，那么他们的距离可直接视为$p \times (p + 1)$。
因为 $t \leq10$ ，因此我们可以直接将大于90的距离直接化为90.
特别的，当$S=T$时，每次只能走$S$步，需特殊判断。
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int L, s, t, m, stone[maxn], add[maxn], dp[maxn];
int far[maxn], ans = 0x3f3f3f3f;
int main()
{
scanf("%d%d%d%d", &L, &s, &t, &m);
for (int i = 1; i <= m; ++i)
scanf("%d", stone + i);
if (s == t)
{
ans = 0;
for (int i = 1; i <= m; ++i)
ans += (stone[i] % s == 0) ? 1 : 0;
//S=T时特判,由于每次走的距离一定,只需判断每个石子位置是否能被S(或T)整除即可
printf("%d", ans);
return 0;
}
sort(stone + 1, stone + m + 1);
stone[0] = 0;
far[m + 1] = min(L - stone[m], 100);//需在最后预留出10的距离,额外让青蛙跳出
L = 0;//重新计算离散化后的L
for (int i = 1; i <= m; ++i)
{
far[i] = min(stone[i] - stone[i - 1], 90);//缩小石子间距离
L += far[i];
add[L] = 1;
}
L += far[m + 1];
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int i = 1; i < L + 10; ++i)
{
for (int j = s; j <= t; ++j)
{
if (i >= j)
dp[i] = min(dp[i], dp[i - j] + add[i]);
}
}
for (int i = L; i < L + 10; ++i) ans = min(ans, dp[i]);//注意在[L,L+10]区间统计答案
printf("%d", ans);
return 0;
}
```