- 卷积神经网络学习笔记——ZFNet(Tensorflow实现)
- 24年3月使用VS22编译TelegramDesktop
- STM32中RFID模块(MFRC522)简单应用
- java反序列化-CC1
$ DP $,是每个信息学竞赛选手所必会的算法,而 $ DP $ 中状态的转移又显得尤为关键。本文主要从状态的设计和转移入手,利用各种方法对朴素 $ DP $ 的时间复杂度和空间复杂度进行优化与处理,以达到满足题目要求的目的; 。
参考文献: 动态规划算法的优化技巧 毛子青 c++ DP总结 《算法竞赛进阶指南》 。
我们都知道,一个题能用 $ DP $ 来解,需要满足以下两个性质:
但对于有些题目,如果要用 $ DP $ 解决的话,会出现环形与后效性的问题; 。
所谓环形与后效性,即状态的转移与 $ DP $ 的方向并不完全一致; 。
举个例子,状态的转移可以从左到右,也可以从右到左,但 $ DP $ 的方向只能为从左到右或从右到左,此时称此 $ DP $ 为有后效性; 。
当状态初能够由状态末转移而来(此时构成了一个环形)时,此时称此 $ DP $ 为环形; 。
对于前者的处理,我们通常会改变 $ DP $ 的遍历方向,使其能够与状态转移的方向一致,当无法一致时,可以使用迭代的方法取得最优解; 。
对于后者,我们通常对初始状态分类讨论,找出几种不是环形的 $ DP $,破环成链,分别处理,最后取最优解; 。
Luogu CF24D Broken robot 。
本题的高斯消元处理 $ DP $ 解法不再叙述,考虑 迭代 $ DP $; 。
设 $ f[i][j] $ 表示从最后一行走到点 $ (i, j) $ 所需的期望步数,则有状态转移方程:
显然,我们 $ DP $ 的方向是向上的,但状态转移的方向是上下左右都有的,所以有后效性,要迭代; 。
#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;
int n, m;
int xx, yy;
double f[1005][1005];
int main() {
cin >> n >> m;
cin >> xx >> yy;
if (xx == n) {
cout << "0.0000000000";
return 0;
}
for (int i = n - 1; i >= xx; i--) {
int tt = 65;
while(tt--) {
if (m == 1) {
f[i][1] = 0.5 * f[i][1] + 0.5 * f[i + 1][1] + 1;
} else {
for (int j = 1; j <= m; j++) {
if (j == 1) {
f[i][j] = 1.0 / 3 * f[i + 1][j] + 1.0 / 3 * f[i][j + 1] + 1.0 / 3 * f[i][j] + 1;
} else if (j == m) {
f[i][j] = 1.0 / 3 * f[i][j - 1] + 1.0 / 3 * f[i + 1][j] + 1.0 / 3 * f[i][j] + 1;
} else {
f[i][j] = 0.25 * f[i][j] + 0.25 * f[i + 1][j] + 0.25 * f[i][j - 1] + 0.25 * f[i][j + 1] + 1;
}
}
}
}
}
cout << fixed << setprecision(4) << f[xx][yy];
return 0;
}
Luogu P6064 Naptime G 。
设计状态 $ f[i][j][k] $ 表示在每 $ N $ 个小时的前 $ i $ 个小时中,休息 $ j $ 个小时,且第 $ j $ 个小时的状态( $ 0 $ 代表醒, $ 1 $ 代表睡),则:
如果我们直接转移的话,初始状态的睡或不睡会影响后面的转移(环形),所以分类讨论:
其中 。
其中 。
最后将两个答案合并起来即可; 。
可以发现,对于环形的分类讨论,状态转移方程基本一样,但初始化会有差异; 。
另外,此题有空间的限制,需要把 $ f $ 数组的第一维用滚动数组滚掉; 。
#include <iostream>
#include <cstring>
using namespace std;
int n, b;
int a[10000005];
int f[2][3831][2]; //0醒, 1睡;
int f1[2][3831][2];
int main() {
cin >> n >> b;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
memset(f, 0xcf, sizeof(f));
memset(f1, 0xcf, sizeof(f1));
f[0][0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= b; j++) {
if (j > i) continue;
f[i & 1][j][0] = max(f[(i - 1) & 1][j][0], f[(i - 1) & 1][j][1]);
f[i & 1][j][1] = max(f[(i - 1) & 1][j - 1][0], f[(i - 1) & 1][j - 1][1] + a[i]);
if (j == 0) f[i & 1][j][1] = 0xcfcfcfcf;
}
}
f1[1][1][1] = a[1];
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= b; j++) {
if (j > i) continue;
f1[i & 1][j][0] = max(f1[(i - 1) & 1][j][0], f1[(i - 1) & 1][j][1]);
f1[i & 1][j][1] = max(f1[(i - 1) & 1][j - 1][0], f1[(i - 1) & 1][j - 1][1] + a[i]);
if (j == 0) f1[i & 1][j][1] = 0xcfcfcfcf;
}
}
cout << max(max(f[n & 1][b][0], f[n & 1][b][1]), f1[n & 1][b][1]);
return 0;
}
倍增优化的关键是找出一个可以随意划分的状态,最后对状态进行拼接得到答案; 。
所谓随意划分,即此状态可以拆分成任意多个长度为 $ 2^n $ 的子状态,且拼接时任意两个子状态不互相影响,并且最后的答案就是要求的正确答案; 。
为什么一个状态能够随意划分成任意多个长度为 $ 2^n $ 的子状态?
对于任意一个正整数,我们可以给他转变成一个二进制数,我们知道,一个二进制数可以表示成 $ 2 $ 的很多次方相加,所以可以; 。
Luogu P1081 [NOIP2012 提高组] 开车旅行 。
本题有三个关键信息:已行驶的天数,所在城市,小A和小B各自行驶的路程长度; 。
若已知出发城市与天数,即可求得小A和小B各自行驶的路程长度,并且依据题意,天数还能反映谁现在在开车,所以我们可以把“天数” 作为“阶段”进行状态设计; 。
定义 $ f[i][j][k] $ 表示从城市 $ j $ 出发,两人共行驶 $ i $ 天,$ k $ 先开车,最终会到达的城市; 。
很显然,这样开会炸内存,而天数又可以随意划分,可以考虑倍增优化; 。
重定义 $ f[i][j][k] $ 表示从城市 $ j $ 出发,两人共行驶 $ 2^i $ 天,$ k $ 先开车,最终会到达的城市; 。
其中 $ 0 $ 代表小A先开车, $ 1 $ 代表小B先开车; 。
对于初始化,我们现在知道谁先开车,要求到那个城市,只需知道小A或小B在某一个城市时,下一个会到哪里即可,可以预处理出两个数组 $ ga[i] $ 和 $ gb[i] $ 分别表示小A在城市 $ i $ 时,下一个会到哪个城市和小B在城市 $ i $ 时,下一个会到哪个城市; 。
对于问题 $ 2 $,我们可以同时维护两个数组 $ da[i][j][k] $ 和 $ db[i][j][k] $ 分别表示从城市 $ j $ 出发,两人共行驶 $ 2^i $ 天,$ k $ 先开车,小A行驶的路程总长度以及小B行驶的路程总长度; 。
对于问题 $ 1 $,我们只需枚举出发点,找最小的即可; 。
则:
因为小A和小B只能往后走,所以我们可以从后往前遍历,并同时维护一个单调递增的序列(可以用 $ multiset $) 其实应该是平衡树,但我不会,每次只需找当前节点旁边一位或两位的最小值和次小值即可(建议参考下面的代码); 。
对于 $ dis $ 的维护,可以在维护单调递增的序列同时顺便维护; 。
这里 $ i = 1 $ 时不同,因为 \(2^1\) 只能拆成两个$ 2^0 $ ,$ 2^0 = 1 $ 是奇数,开车的人不同,其它的是偶数,开车的人相同; 。
#include <iostream>
#include <set>
#include <cmath>
using namespace std;
int n;
int h[10000005];
int x0, m;
struct sss{
long long id, he;
bool operator <(const sss &A) const {
return he < A.he;
}
};
long long f[18][100005][2]; // 0 a, 1 b;
long long da[18][100005][2];
long long db[18][100005][2];
multiset<sss> p;
void init() {
p.insert({0, 9999999999999999});
p.insert({0, 9999999999999999});
p.insert({n + 1, -9999999999999999});
p.insert({n + 1, -9999999999999999}); //防止访问越界
for (long long i = n; i >= 1; i--) {
long long ga, gb;
p.insert({i, h[i]});
multiset<sss>::iterator q = p.lower_bound({i, h[i]});
q--;
long long lid = (*q).id, lh = (*q).he;
q++;
q++;
long long rid = (*q).id, rh = (*q).he;
q--;
if (abs(rh - h[i]) >= abs(lh - h[i])) {
gb = lid;
q--; q--;
if (abs(rh - h[i]) < abs((*q).he - h[i])) {
ga = rid;
} else {
ga = (*q).id;
}
} else {
gb = rid;
q++; q++;
if (abs((*q).he - h[i]) < abs(lh - h[i])) {
ga = (*q).id;
} else {
ga = lid;
}
}
f[0][i][0] = ga;
f[0][i][1] = gb;
da[0][i][0] = abs(h[ga] - h[i]);
db[0][i][1] = abs(h[gb] - h[i]);
}
}
pair<long long, long long> w(long long s, long long x) {
long long p = s;
long long la = 0;
long long lb = 0;
for (int i = 17; i >= 0; i--) {
if (f[i][p][0] && la + lb + da[i][p][0] + db[i][p][0] <= x) {
la += da[i][p][0];
lb += db[i][p][0];
p = f[i][p][0];
}
}
return {la, lb};
}
int main() {
cin >> n;
for (long long i = 1; i <= n; i++) cin >> h[i];
cin >> x0;
cin >> m;
init();
long long tt = 10;
for (int i = 1; i <= 17; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 0; k <= 1; k++) {
if (i == 1) {
f[i][j][k] = f[0][f[0][j][k]][1 - k];
da[i][j][k] = da[0][f[0][j][k]][1 - k] + da[0][j][k];
db[i][j][k] = db[0][f[0][j][k]][1 - k] + db[0][j][k];
} else {
f[i][j][k] = f[i - 1][f[i - 1][j][k]][k];
da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k];
db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k];
}
}
}
}
long double ans = 1.00 * 0x3f3f3f3f;
long long an = 0;
for (int i = 1; i <= n; i++) {
pair<long long, long long> a = w(i, x0);
long long la = a.first;
long long lb = a.second;
if (lb == 0) continue;
long double d = 1.00 * la / (1.00 * lb);
if (d < ans) {
ans = d;
an = i;
} else if (d == ans) {
if (h[an] < h[i]) an = i;
}
}
cout << an << endl;
long long a, b;
for (int i = 1; i <= m; i++) {
cin >> a >> b;
pair<long long, long long> c = w(a, b);
cout << c.first << ' ' << c.second << endl;
}
return 0;
}
一般在设计出状态以后,发现空间复杂度不符合要求,且有状态能够随意划分,则可以使用倍增优化; 。
适用范围:
时间复杂度能够忍受 $ \Theta (n \ log \ n) $ 。
状态转移方程中要维护 $ \max $ 或 $ \min $ 或 $ sum $ 且区间固定; 。
一般使用线段树或树状数组 。
Luogu P4644 [USACO05DEC] Cleaning Shifts S 。
我们可以定义 $ f[i] $ 表示到第 $ i $ 个时间点时的最小花费,我们用一个结构体存储每头牛的信息($ st $ 为开始时刻,$ ed $为结束时刻, $ w $ 为工资),显然有状态转移方程:
我们发现, $ DP $ 的方向是按照 $ ed $ 的顺序从左向右走的,所以先要将结构体按 $ ed $ 的顺序排序; 。
时间复杂度:$ \Theta (n^2) $ 极限数据会被卡; 。
考虑优化; 。
发现状态转移方程有这一项:
对于一个区间固定求最小值的操作,很容易想到用线段树维护; 。
具体实现方法:
使用线段树查询区间 $ [e[i].st - 1, e[i].ed] $ 的最小值并更新(注意这里要取到 $ e[i].ed $ 因为后面要插入 $ f[i] $ ,这样做继承了原来的最小值,便于后面更新); 。
状态转移 。
这里的 $ ask $ 是线段树的询问操作; 。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct sss{
int st, ed, w;
bool operator <(const sss &A) const {
return ed < A.ed;
}
}e[10000005];
inline int ls(int x) {
return x << 1;
}
inline int rs(int x) {
return x << 1 | 1;
}
struct sas{
int l, r, mi;
}tr[90000005];
int n, m, t;
int f[10000005];
void bt(int id, int l, int r) {
tr[id].l = l;
tr[id].r = r;
if (l == r) {
tr[id].mi = f[l];
return;
}
int mid = (l + r) >> 1;
bt(ls(id), l, mid);
bt(rs(id), mid + 1, r);
tr[id].mi = min(tr[ls(id)].mi, tr[rs(id)].mi);
}
int ask(int id, int l, int r) {
if (r < l) return 0x3f3f3f3f;
if (tr[id].l >= l && tr[id].r <= r) {
return tr[id].mi;
}
int mid = (tr[id].l + tr[id].r) >> 1;
if (r <= mid) return ask(ls(id), l, r);
else if (l > mid) return ask(rs(id), l, r);
else return min(ask(ls(id), l, mid), ask(rs(id), mid + 1, r));
}
void add(int id, int pos, int d) {
if (tr[id].l == tr[id].r) {
tr[id].mi = d;
return;
}
int mid = (tr[id].l + tr[id].r) >> 1;
if (pos <= mid) add(ls(id), pos, d);
else add(rs(id), pos, d);
tr[id].mi = min(tr[ls(id)].mi, tr[rs(id)].mi);
}
int main() {
cin >> n >> m >> t;
m++;
t++;
bool vi = false;
for (int i = 1; i <= n; i++) {
cin >> e[i].st >> e[i].ed >> e[i].w;
e[i].st++;
e[i].ed++; //将时间段转化为时间点
}
sort(e + 1, e + 1 + n);
memset(f, 0x3f, sizeof(f));
f[m - 1] = 0;
bt(1, m - 1, t);
for (int i = 0; i <= n; i++) {
f[e[i].ed] = min(f[e[i].ed], ask(1, e[i].st - 1, e[i].ed) + e[i].w);
add(1, e[i].ed, f[e[i].ed]);
}
if (f[t] == 0x3f3f3f3f) { //判断能不能被更新
cout << -1;
} else {
cout << f[t];
}
return 0;
}
类比数据结构优化,单调队列优化的特征为区间不固定(滑动窗口),队列头部在保证合法的状态下,是现在的最优决策,在尾部将每次更新的决策插入,同时维护队列的单调性; 。
适用范围:1D/1D动态规划 。
所谓1D/1D动态规划,即状态转移方程形如 。
的动态规划,
对于纯单调队列的优化,其中 $ val(i, j) $ 的每一项仅与 $ i $ 和 $ j $ 之中的一个有关(即不能出现 $ i $ 和 $ j $ 的乘积项),这是用单调队列优化的基本条件; 。
单调队列优化的基本思路:
对于一个状态 $ i $,我们要做的就是在决策范围单调变化的同时,快速找出一个最优决策 $ j $,然后更新现在的状态,单调队列就是在维护这样一个合法的决策集合,使我们能够快速更新现在的状态; 。
依据这个思路,我们来分析一下时间复杂度:
假设现在 $ i \in [1, n] $,则:
朴素:枚举一次 $ i $ ,同时内层循环枚举 $ j \in [l(i), r(i)] $(一般是 $ j \in [0, i) $ ),时间复杂度为 $ \Theta (n^2) $; 。
单调队列优化:每个 $ j $ 至多进队和出队一次,时间复杂度为 $ \Theta (n) $; 。
Luogu P2254 [NOI2005] 瑰丽华尔兹 。
首先很容易想出一个状态 $ f[k][i][j] $ 代表在第 $ k $ 时刻,在 $ (i, j) $ 所滑行的最长距离; 。
很容易想出状态转移方程:
其中,$ t[k] $ 代表滑行方向; 。
可以用滚动数组将第一位滚掉以满足内存需求; 。
时间复杂度:$ \Theta (Tnm) $ 需要优化; 。
不妨从状态设计下手,发现时间段的范围很小,所以可以重定义状态 $ f[k][i][j] $ 代表在第 $ k $ 个时间段,在 $ (i, j) $ 所滑行的最长距离; 。
状态转移方程:
发现时间复杂度 $ \Theta (kn^2 m^2) $ 需要优化; 。
不难发现,对于一个相同的时间段,移动的方向是固定的,且随着 $ (i, j) $ 的变化,决策的范围也在单调变化,且 $ dis $ 仅和 $ i $ 与 $ j $ 有关,所以对于 $ dis $ 可以用单调队列优化; 。
具体实现操作:
分情况确定移动的方向; 。
在此方向维护一个单调队列存相应的决策 $ j $,每次更新时首先判断队头是否越界(即 $ dis $ 是否大于时间段),如果越界,弹出队头; 。
队头即为最优决策,用队头更新当前状态; 。
将当前状态作为决策从队尾插入,同时维护单调性; 。
注意: 单调队列中维护的是决策(即状态转移方程中的 $ j $),每次进行第 $ 4 $ 步时需要将决策带回状态转移方程进行判断; 。
第一维可以用滚动数组滚掉; 。
具体实现请看代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>
#include <cmath>
using namespace std;
int n, m, x, y, kk;
int a[505][505];
int t[40005];
int f[2][205][205];
int T;
char c;
struct sss{
int st, ed, d;
}e[10000005];
deque<int> q;
int main() {
cin >> n >> m >> x >> y >> kk;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
if (c == '.') {
a[i][j] = 1;
}
if (c == 'x') {
a[i][j] = 0;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[0][i][j] = 0xcfcfcfcf;
}
}
f[0][x][y] = 0;
int p = 0;
for (int i = 1; i <= kk; i++) {
cin >> e[i].st >> e[i].ed >> e[i].d;
}
for (int k = 1; k <= kk; k++) {
p ^= 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[p][i][j] = 0xcfcfcfcf;
}
}
if (e[k].d == 3) {
for (int i = 1; i <= n; i++) {
q.clear(); //注意每次清空队列;
for (int j = m; j >= 1; j--) {
if (a[i][j] == 0) {
q.clear(); //碰到障碍物后,前面的决策都不可取,所以要清空队列;
continue;
}
while(!q.empty() && q.front() > j + (e[k].ed - e[k].st + 1)) q.pop_front();
while(!q.empty() && f[p ^ 1][i][j] + j >= f[p ^ 1][i][q.back()] + q.back()) q.pop_back();
q.push_back(j);
f[p][i][j] = max(f[p][i][j], f[p ^ 1][i][q.front()] + q.front() - j);
}
}
}
else if (e[k].d == 4) {
for (int i = 1; i <= n; i++) {
q.clear();
for (int j = 1; j <= m; j++) {
if (a[i][j] == 0) {
q.clear();
continue;
}
while(!q.empty() && q.front() < j - (e[k].ed - e[k].st + 1)) q.pop_front();
while(!q.empty() && f[p ^ 1][i][j] - j >= f[p ^ 1][i][q.back()] - q.back()) q.pop_back();
q.push_back(j);
f[p][i][j] = max(f[p][i][j], f[p ^ 1][i][q.front()] + j - q.front());
}
}
}
else if (e[k].d == 1) {
for (int j = 1; j <= m; j++) {
q.clear();
for (int i = n; i >= 1; i--) {
if (a[i][j] == 0) {
q.clear();
continue;
}
while(!q.empty() && q.front() > i + (e[k].ed - e[k].st + 1)) q.pop_front();
while(!q.empty() && f[p ^ 1][i][j] + i >= f[p ^ 1][q.back()][j] + q.back()) q.pop_back();
q.push_back(i);
f[p][i][j] = max(f[p][i][j], f[p ^ 1][q.front()][j] + q.front() - i);
}
}
}
else if (e[k].d == 2) {
for (int j = 1; j <= m; j++) {
q.clear();
for (int i = 1; i <= n; i++) {
if (a[i][j] == 0) {
q.clear();
continue;
}
while(!q.empty() && q.front() < i - (e[k].ed - e[k].st + 1)) q.pop_front();
while(!q.empty() && f[p ^ 1][i][j] - i >= f[p ^ 1][q.back()][j] - q.back()) q.pop_back();
q.push_back(i);
f[p][i][j] = max(f[p][i][j], f[p ^ 1][q.front()][j] - q.front() + i);
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ans = max(ans, f[p][i][j]);
}
}
cout << ans;
return 0;
}
不难发现,在单调队列优化时,我们通常将状态看做常量,将决策看做变量,每次保证决策的单调性,是做这部分题的小技巧; 。
推荐一道题 。
Luogu P2569 [SCOI2010] 股票交易 。
刚刚我们探讨了单调队列优化的基本操作,让我们回顾一下1D/1D动态规划的状态转移方程:
我们知道,当$ val(i, j) $ 的每一项仅与 $ i $ 和 $ j $ 之中的一个有关(即不能出现 $ i $ 和 $ j $ 的乘积项)时,可以用单调队列优化; 。
如果有乘积项,就需要用到斜率优化; 。
当出现乘积项时,我们很容易联想到平面直角坐标系中形如 $ y = kx + b $ 的一次函数,依据这个思想,我们来探讨斜率优化; 。
斜率优化的主要思想:及时排除无用决策; 。
接下来,我们依据例题来解释斜率优化; 。
Luogu P5785 [SDOI2012] 任务安排 。
首先求出 $ T $, $ C $ 的前缀和 $ sumt $ 和 $ sumc $ ; 。
定义$ f[i][j] $ 表示前 $ i $ 个任务分成 $ j $ 批施行的最小费用,很容易得出状态转移方程:
时间复杂度:$ \Theta (n^3) $ 。
考虑优化; 。
不妨设题目中 $ t $ 都为正整数; 。
不难发现,状态的第二维(批次)是一个附加状态,即它不是求答案的直接手段,只是求答案的一个附加手段; 。
考虑优化掉这一维; 。
其实当我们在执行一批任务时,并不是关心它之前机器启动了多少次,而是应该关心机器的启动对现在状态所耽误的时间; 。
如果不知道之前机器启动了多少次,怎么去求机器的启动对现在状态所耽误的时间?
我们可以换一个角度思考,机器因执行一批任务所花费的启动时间 $ S $ 会累加到后续所有任务完成的时间之中,对此,我们引入一个思想,叫做费用提前计算,也就是说,当每启动一次机器时,就把它对之后的所有影响(一直到 $ n $)全部计算在内,这样就达到了求出最小费用的优化; 。
依据上述思路,我们定义 $ f[i] $ 表示把前 $ i $ 个任务分成若干批执行的最小费用,有状态转移方程:
值得注意的是,在费用提前计算的思想下,只有目标 $ f[n] $ 是正确的,其它结果(例如 $ f[n - 1] $)是偏大的; 。
时间复杂度:$ \Theta (n^2) $ 。
还是不行,再次考虑优化; 。
发现这个优化过的状态转移方程满足1D/1D的动态规划,且 $ val $ 项有乘积项,考虑斜率优化; 。
将方程展开,得到:
因为在平面直角坐标系中,纵坐标是随横坐标变化的,所以我们去掉 $ \min $,将只含 $ j $ 的项移到等式左面,剩下的项移到等式右面,可得:
在以 $ sumc[j] $ 为横坐标,$ f[j] $ 为纵坐标的平面直角坐标系中,这是一条以 $ S + sumt[i] $ 为斜率,$ f[i] - sumt[i] * sumc[i] - S * sumc[n] $ 为截距的直线; 。
这也就是说,我们的决策其实也就对应这个平面直角坐标系中的一个个点,这条直线就对应着我们现在的状态,要用决策去更新状态,需要让这条线去撞决策点; 。
如图所示; 。
现在我们想要让 $ f[i] $ 最小,观察得截距中其它项都是常数,那么我们让截距最小,所经过的点即为最优决策; 。
现在我们来考虑一个点能成为最优决策的条件,并依此排除无用决策; 。
如图,发现当这三个点构成一个“上凸”形时,点 $ 2 $ 不可能成为最优决策; 。
如图,发现当这三个点构成一个“下凸”形时,这三个点都可能成为最优决策; 。
发现:一个决策点 $ 2 $ 能够成为最优决策,当且仅当:
这里有个技巧,当我们求斜率时,最好保证两边都为正数,以省去不必要的计算与变号 。
当取等号时, \(j_2\) 与 \(j_3\) 同时成为最优决策; 。
于是,我们只需用单调队列维护一个下凸壳(如第二张图)即可,其中斜率单调递增; 。
当我们找最优决策时,可以发现最优决策点与左边点的连线斜率比 $ S + sumt[i] $ 小,右边比它大; 。
所以,总的操作为:
检查队首斜率与直线斜率 $ S + sumt[i] $ 的关系,若前者小于等于后者,根据斜率 $ S + sumt[i] $ 的单调递增性,需使队首出队; 。
此时,队首即为最优决策,更新现在的状态; 。
依据 $ sumc[j] $ 的单调递增性,我们从队尾将已经更新的状态作为一个新的决策插入,同时维护决策斜率的单调递增性; 。
在进行第三步时,我们将 $ i $ 与队尾建立联系,求出斜率,同时将此斜率与队尾斜率进行比较,以维护斜率的单调递增性; 。
时间复杂度优化到了 $ \Theta (n) $; 。
到这,实现的代码为:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, s;
int t[1000005], c[1000005];
int f[1000005];
int sumt[1000005], sumc[1000005];
int main() {
cin >> n >> s;
for (int i = 1; i <= n; i++) cin >> t[i] >> c[i];
sumt[1] = t[1];
sumc[1] = c[1];
for (int i = 1; i <= n; i++) {
sumt[i] = sumt[i - 1] + t[i];
sumc[i] = sumc[i - 1] + c[i];
}
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
f[i] = min(f[i], f[j] + sumt[i] * (sumc[i] - sumc[j]) + s * (sumc[n] - sumc[j]));
}
}
cout << f[n];
return 0;
}
但我们讨论的都是 $ t $ 都为正整数的情况,如果不是呢(即 $ sumt $ 并不是单调递增的)?
很显然,我们上述过程中的第一步就不对了,那也没有关系,此时问题是队首不一定是最优决策,所以我们不能弹出队首,而必须维护整个凸壳,依据决策斜率的单调性,每次二分查找满足上述过程中的第一步并更新即可; 。
队尾操作不变; 。
时间复杂度:$ \Theta (n \ log \ n) $,可以通过本题; 。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long
int n, s;
int t[1000005], c[1000005];
int f[1000005];
int sumt[1000005], sumc[1000005];
int q[10000005];
int l, r;
int bi(int k) {
if (l == r) return q[l];
int L = l, R = r;
while(L <= R) {
int mid = (L + R) >> 1;
if (f[q[mid + 1]] - f[q[mid]] <= k * (sumc[q[mid + 1]] - sumc[q[mid]])) L = mid + 1;
else R = mid - 1;
}
return q[L];
}
main() {
cin >> n >> s;
for (int i = 1; i <= n; i++) cin >> t[i] >> c[i];
sumt[1] = t[1];
sumc[1] = c[1];
for (int i = 1; i <= n; i++) {
sumt[i] = sumt[i - 1] + t[i];
sumc[i] = sumc[i - 1] + c[i];
}
memset(f, 0x3f, sizeof(f));
f[0] = 0;
l = 0, r = 0;
q[0] = 0;
for (int i = 1; i <= n; i++) {
int j = bi(s + sumt[i]);
f[i] = min(f[i], f[j] - (s + sumt[i]) * sumc[j] + sumt[i] * sumc[i] + s * sumc[n]);
while(l < r && (f[q[r]] - f[q[r - 1]]) * (sumc[i] - sumc[q[r]]) >= (f[i] - f[q[r]]) * (sumc[q[r]] - sumc[q[r - 1]])) r--;
q[++r] = i;
}
cout << f[n];
return 0;
}
推荐题目 。
Luogu CF311B Cats Transport 。
斜率优化一般会结合前缀和,在求解斜率时,可以化除为乘,但不易查错。也可以将斜率写为函数,但容易丢精度; 。
四边形不等式定义:
其中 $ w(a, b) $ 表示定义在整数集合上的二元函数; 。
对于形如 。
的状态转移方程,设 $ p[i] $ 是 $ f[i] $ 的最优决策,若 $ p $ 在定义域内单调不减,则称 $ f $ 具有决策单调性; 。
在状态转移方程 。
中,若函数 $ val $ 满足四边形不等式,则称 $ f $ 具有决策单调性; 。
显然,在 $ p $ 数组中,决策是连续的,如图:
这显示了 $ p $ 数组中存储的决策; 。
维护一个三元组 $ j, l, r $, $ j $ 代表当前段内的决策,$ l $ $ r $ 分别代表当前决策的左右区间(管辖范围); 。
用单调队列维护 $ p $ 数组,可以概括为以下几个步骤:
设队尾三元组为 $ j_0, l_0, r_0 $,则:
若对于 $ f[l_0] $ 来说,$ i $ 比 $ j_0 $ 更优,则删除队尾; 。
否则,在队尾二分查找,找到一个位置,使得在这个位置及右边 $ i $ 比 $ j_0 $ 更优,左边$ j_0 $ 比 $ i $ 更优,这个位置记为 $ pos $; 。
将三元组 $ i, pos, n $ 插入队尾; 。
概括来讲,$ DP $ 优化思路为:
有可随意划分的,用倍增优化; 。
发现环形,破环成链,或者复制一倍在末尾,用环形处理的思路; 。
状态转移的方向与 $ DP $ 方向不一,用后效性处理的思路; 。
状态转移方程需要在定区间内查询最值等等,用数据结构优化; 。
1D/1D的动态规划,需要维护动态区间,当 $ val $ 中有乘积项时,用斜率优化。没有时用单调队列优化; 。
当 $ val $ 满足四边形不等式时,依据决策的单调性优化; 。
总之, $ DP $ 优化因题而异,做好优化需要我们快速且正确的设计出状态转移方程,打好基础,才能做到掌握优化; 。
最后此篇关于[DP]DP优化总结的文章就讲到这里了,如果你想了解更多关于[DP]DP优化总结的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
比较代码: const char x = 'a'; std::cout > (0C310B0h) 00C3100B add esp,4 和 const i
您好,我正在使用 Matlab 优化求解器,但程序有问题。我收到此消息 fmincon 已停止,因为目标函数值小于目标函数限制的默认值,并且约束满足在约束容差的默认值范围内。我也收到以下消息。警告:矩
处理Visual Studio optimizations的问题为我节省了大量启动和使用它的时间 当我必须进行 J2EE 开发时,我很难回到 Eclipse。因此,我还想知道人们是否有任何提示或技巧可
情况如下:在我的 Excel 工作表中,有一列包含 1-name 形式的条目。考虑到数字也可以是两位数,我想删除这些数字。这本身不是问题,我让它工作了,只是性能太糟糕了。现在我的程序每个单元格输入大约
这样做有什么区别吗: $(".topHorzNavLink").click(function() { var theHoverContainer = $("#hoverContainer");
这个问题已经有答案了: 已关闭11 年前。 Possible Duplicate: What is the cost of '$(this)'? 我经常在一些开发人员代码中看到$(this)引用同一个
我刚刚结束了一个大型开发项目。我们的时间紧迫,因此很多优化被“推迟”。既然我们已经达到了最后期限,我们将回去尝试优化事情。 我的问题是:优化 jQuery 网站时您要寻找的最重要的东西是什么。或者,我
所以我一直在用 JavaScript 编写游戏(不是网络游戏,而是使用 JavaScript 恰好是脚本语言的游戏引擎)。不幸的是,游戏引擎的 JavaScript 引擎是 SpiderMonkey
这是我在正在构建的页面中使用的 SQL 查询。它目前运行大约 8 秒并返回 12000 条记录,这是正确的,但我想知道您是否可以就如何使其更快提出可能的建议? SELECT DISTINCT Adve
如何优化这个? SELECT e.attr_id, e.sku, a.value FROM product_attr AS e, product_attr_text AS a WHERE e.attr
我正在使用这样的结构来测试是否按下了所需的键: def eventFilter(self, tableView, event): if event.type() == QtCore.QEven
我正在使用 JavaScript 从给定的球员列表中计算出羽毛球 double 比赛的所有组合。每个玩家都与其他人组队。 EG。如果我有以下球员a、b、c、d。它们的组合可以是: a & b V c
我似乎无法弄清楚如何让这个 JS 工作。 scroll function 起作用但不能隐藏。还有没有办法用更少的代码行来做到这一点?我希望 .down-arrow 在 50px 之后 fade out
我的问题是关于用于生产的高级优化级联样式表 (CSS) 文件。 多么最新和最完整(准备在实时元素中使用)的 css 优化器/最小化器,它们不仅提供删除空格和换行符,还提供高级功能,如删除过多的属性、合
我读过这个: 浏览器检索在 中请求的所有资源开始呈现 之前的 HTML 部分.如果您将请求放在 中section 而不是,那么页面呈现和下载资源可以并行发生。您应该从 移动尽可能多的资源请求。
我正在处理一些现有的 C++ 代码,这些代码看起来写得不好,而且调用频率很高。我想知道我是否应该花时间更改它,或者编译器是否已经在优化问题。 我正在使用 Visual Studio 2008。 这是一
我正在尝试使用 OpenGL 渲染 3 个四边形(1 个背景图,2 个 Sprite )。我有以下代码: void GLRenderer::onDrawObjects(long p_dt) {
我确实有以下声明: isEnabled = false; if(foo(arg) && isEnabled) { .... } public boolean foo(arg) { some re
(一)深入浅出理解索引结构 实际上,您可以把索引理解为一种特殊的目录。微软的SQL SERVER提供了两种索引:聚集索引(clustered index,也称聚类索引、簇集索引)和非聚集索引(no
一、写在前面 css的优化方案,之前没有提及,所以接下来进行总结一下。 二、具体优化方案 2.1、加载性能 1、css压缩:将写好的css进行打包,可以减少很多的体积。 2、css单一样式:在需要下边
我是一名优秀的程序员,十分优秀!