广元市建设局网站,建设网站的一些基本代码,软件网页制作,网站商城注意事项目录 四边形不等式内容[HNOI2008]玩具装箱解析代码实现 参考资料 四边形不等式内容
TODO
[HNOI2008]玩具装箱
解析
满足四边形不等式#xff0c;决策具有单调性. 对于两个位置 i , j i, j i,j, 对应的最优决策点一定有 o p t [ i ] o p t [ j ] opt[i] opt[j]… 目录 四边形不等式内容[HNOI2008]玩具装箱解析代码实现 参考资料 四边形不等式内容
TODO
[HNOI2008]玩具装箱
解析
满足四边形不等式决策具有单调性. 对于两个位置 i , j i, j i,j, 对应的最优决策点一定有 o p t [ i ] o p t [ j ] opt[i] opt[j] opt[i]opt[j]代码实现 需要有一个队列这里我们使用c里的双端队列( d e q u e deque deque). 因为需要在队尾插入和弹出队首弹出的操作.初始化时队列里只有一个元素, 比如本题中区间 [ 1 , n ] [1, n] [1,n], 决策点为 0 0 0. 这个对所有的位置 [ 1 , n ] [1, n] [1,n]都是合法的一个决策每次插入决策 x x x的时候从队尾开始判断如果当前的节点的区间的开始位置决策 x x x更优就弹出队尾一直这么做.接上一步, 于是就找到了一个节点(当前队尾): 对应的区间开始位置 x x x不优结束位置 x x x更优。所以存在一个临界点我们二分就是要找这么一个位置 p o s pos pos. [ p o s , n ] [pos, n] [pos,n]这部分 x x x更优其他位置不变.主函数循环部分我们维持队列的区间都是还未确定最优决策的部分。主函数循环部分当循环到位置 i i i时候由于我们已经考虑过小于 i i i的所有决策因此对于位置 i i i队首的决策就是位置 i i i的最优决策.
代码实现
#include bits/stdc.h
using namespace std;#ifdef LOCAL
#include debug.h
#else
#define debug(...) 42
#endifconst int N 5e4 5;typedef long long LL;int n, L;
// 原数组以及前缀和
vectorLL a, sum;
// dp[i]: 前i个玩具的最小费用. dp[i] min(dp[j] (s[i] - s[j] i - j - 1 - L)^2), 0 j i
vectorLL dp;
// f[i]的最优决策点是谁, 也就是f[i]取得最小值的时候对应的上面的式子中的j. opt[i] j.
vectorint op;struct Node {int l, r, c;Node(int _l, int _r, int _c): l(_l), r(_r), c(_c){}
};// 存在插入队尾,弹出队首,弹出队尾三种操作,因此我们使用deque
dequeNode q;// dp方程: f[j] f[i] (x - L) ^ 2
inline LL val(int j, int i) {LL s sum[i] - sum[j] i - j - 1 - L;return dp[j] 1LL * s * s;
}// 用决策x更新
void insert(int x) {// pos表示能更新的那一段的开始位置, 结束位置一定是nint pos n 1; // 临界点// 找到x能更新的队列一定是末尾的一段// 队列里队尾的元素. 看决策x是否是更优的决策. 满足意味着x更优while (q.size() val(x, q.back().l) val(q.back().c, q.back().l)) {pos q.back().l; // 更新pos: [q,back().l, q.back().r] 这一段肯定x更优q.pop_back();}// 找到了这个区间. 这个区间的右边界x更优,左边界x不优秀. 我们二分寻找临界点在哪里if (q.size() val(x, q.back().r) val(q.back().c, q.back().r)) {int l q.back().l, r q.back().r;while (l r) {int mid l r 1;if (val(x, mid) val(q.back().c, mid)) r mid; // 对于mid这个点, x的决策更优, 临界点在左边 - [l, mid]else l mid 1; // mid这个点,x不优. 那么临界点在右半部分 - [mid 1, r]}// 结束循环时,r是使x成为最优决策的一段的起始位置pos r;q.back().r r - 1;}// 说明存在某些位置x的决策比当前队列的优. 也就是进入过上面的代码.if (pos ! n 1) q.push_back(Node(pos, n, x));
}int main() {cin n L;a sum dp vectorLL(n 1, 0);op vectorint(n 1, 0);for (int i 1; i n; i) cin a[i], sum[i] sum[i - 1] a[i];q.push_back(Node(1, n, 0)); // 一开始队列只有一个元素表示[1, n]所有的最优决策点都是0for (int i 1; i n; i) {// 队头的决策点就是当前i的最优决策int opt q.front().c;dp[i] val(opt, i);op[i] opt;// 弹出已经无用的决策if (q.front().r i) q.pop_front();q.front().l i 1;// 插入当前决策,并用决策i去更新 [i 1, n]的最优决策insert(i);}cout dp[n] endl;return 0;
}参考资料
OIWIKI洛谷日报
