首页 > 其他分享 >CEOI2017 Building Bridges

CEOI2017 Building Bridges

时间:2023-07-20 18:57:34浏览次数:45  
标签:Building Bridges ch int CEOI2017 gety maxn id define

小清新斜率优化题。

分段问题显然 dp,令 \(f_i\) 为将第 \(1\) 根柱子和第 \(i\) 根柱子连接的最小代价。\(f_1=0\),每次枚举 \(i\) 向前直接连接的柱子:

\[f_{i}=\min\limits_{j=1}^{i-1}\left\{f_j+(h_i-h_j)^2+\sum\limits_{k=j+1}^{i-1}w_k\right\} \]

令 \(s_{i}=\sum\limits_{j=1}^iw_j\),然后把转移拆开,假设最优决策点为 \(j\):

\[f_i=f_j+(h_i-h_j)^2+s_{i-1}-s_{j} \]

\[f_i=f_j+h_i^2+h_j^2-2h_jh_i+s_{i-1}-s_{j} \]

\[f_{i}-s_{i-1}-h_i^2=f_j-s_j+h_j^2-2h_j\times h_i \]

平凡的斜率优化会把上式写成 \(b=y-xk\) 的形式,但我们旋转一下坐标系,令 \(y_i=f_{i}-s_{i-1}-h_{i}^2\),\(b_j=f_j-s_j+h_j^2\),\(k_j=-2h_j\),\(x_i=h_i\):

\[y_i=k_jx_i+b_j \]

于是我们得到了斜率优化的另一种形式。

我们可以将转移点 \(j\) 看作平面上的一条条形如 \(y=k_jx+b_j\) 的直线,每次即查询一个 \(x\) 坐标上 \(y\) 坐标最小的值,支持动态插入一条直线。

李超线段树维护即可。复杂度 \(O(n\log w)\)。

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace vbzIO {
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
	#else
	#define gh() getchar()
	#endif
	#define pi pair<int, int>
	#define mp make_pair
	#define fi first
	#define se second
	#define pb push_back
	#define ins insert
	#define era erase
	inline int read () {
		char ch = gh();
		int x = 0;
		bool t = 0;
		while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
		return t ? ~(x - 1) : x;
	}
	inline void write(int x) {
		if (x < 0) {
			x = ~(x - 1);
			putchar('-');
		}
		if (x > 9)
			write(x / 10);
		putchar(x % 10 + '0');
	}
}
using vbzIO::read;
using vbzIO::write;

const int maxn = 1e5 + 100;
const int maxw = 1e6 + 100;
const int inf = 1e18;
int n, h[maxn], w[maxn], s[maxn], f[maxn], tr[maxw << 2];

#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
int K(int id) { return - 2 * h[id]; }
int B(int id) { return id ? (f[id] - s[id] + h[id] * h[id]) : inf; }
int gety(int id, int x) { return K(id) * x + B(id); }
int cmp(int x, int y) { return x == y ? 0 : (x > y ? 1 : -1); }
void push(int l, int r, int s, int x) {
    int &t = tr[x];
    if (cmp(gety(s, mid), gety(t, mid)) == -1) swap(s, t);
    int fl = cmp(gety(s, l), gety(t, l)), fr = cmp(gety(s, r), gety(t, r));
    if (fl == -1 || (!fl && s < t)) push(l, mid, s, ls);
    if (fr == -1 || (!fr && s < t)) push(mid + 1, r, s, rs);
}

int qry(int l, int r, int p, int x) {
    if (l == r) return gety(tr[x], p);
    int res = gety(tr[x], p);
    if (p <= mid) return min(res, qry(l, mid, p, ls));
    else return min(res, qry(mid + 1, r, p, rs));
}

signed main() {
	n = read();
    for (int i = 1; i <= n; i++) h[i] = read();
    for (int i = 1; i <= n; i++) w[i] = read(), s[i] = s[i - 1] + w[i];
    push(0, 1e6, 1, 1);
    for (int i = 2; i <= n; i++) {
        int j = qry(0, 1e6, h[i], 1);
        f[i] = j + s[i - 1] + h[i] * h[i];
        push(0, 1e6, i, 1);
    }
    write(f[n]);
	return 0;
}

标签:Building,Bridges,ch,int,CEOI2017,gety,maxn,id,define
From: https://www.cnblogs.com/Ender32k/p/17569087.html

相关文章

  • [LeetCode] 2222. Number of Ways to Select Buildings
    Youaregivena 0-indexed binarystring s whichrepresentsthetypesofbuildingsalongastreetwhere:s[i]='0' denotesthatthe ith buildingisanofficeands[i]='1' denotesthatthe ith buildingisarestaurant.Asacityoff......
  • Building Bridges 题解
    BuildingBridges题目大意连接两根柱子\(i,j\)的代价是\((h_i-h_j)^2+\sum\limits_{k=j+1}^{i-1}w_k\),连接具有传递性,求将\(1,n\)连接的最小代价。思路分析斜率优化DP板题。设\(f_i\)表示考虑到前\(i\)根柱子并强制选择第\(i\)根柱子的最小代价,所求即\(f_n\)。......
  • 【DP】DMOPC '21 Contest 8 P5 - Tree Building
    ProblemLink给定\(n,m\)和一个长为\(m\)的代价序列,对于一棵\(n\)个节点,每个节点度数不超过\(m\)的树,定义它的代价为\(\sum\limits_{i=1}^na_{deg_i}\)。求代价最小的树的代价。\(n\le10^9,m\le3000,1\lea_i\le10^9\)。首先一眼变成选出\(n\)个\(a\)的和为......
  • 内核文档翻译 —— Building External Modules(编译外部模块)
    原文:https://www.kernel.org/doc/html/latest/kbuild/modules.htmlThisdocumentdescribeshowtobuildanout-of-treekernelmodule.1.Introduction"kbuild"isthebuildsystemusedbytheLinuxkernel.Modulesmustusekbuildtostaycompatiblewi......
  • Building a Dice Game using JavaScript Javascript构建一个dice game 项目
    WewillbebuildingaDiceGameProjectusingHTML,CSS,andJavaScript.TheDiceGameisbasedonatwo-player.Bothplayersrollthediceandtheplayerwhogetsthehighestphasevaluewillwinthegame.ImagesofDicePhases: Thelistofdicephasesi......
  • ERROR: Failed building wheel for mysqlclient Running setup.py clean for mysqlc
    Itseemsthatthereisanerrorwhiletryingtoinstallthemysqlclientpackageandit'sfailingtobuildthewheel.Theerrormessageindicatesthatitcan'tfindthePython.hfile,whichisrequiredforbuildingCextensions.Toresolvethisi......
  • RuntimeError: Error building extension ‘fused‘&FAILED: fused_bias_act_kernel.c
    RuntimeError:Errorbuildingextension‘fused’&FAILED:fused_bias_act_kernel.cuda.o&ninja:buildstopped:subcommandfailed.问题如下:RuntimeError:Errorbuildingextension‘fused’:[1/3]/usr/local/cuda/bin/nvcc-DTORCH_EXTENSION_NAME=fused-DTORCH_......
  • [CEOI2017] Sure Bet(双指针)
    题目大意:给出两个数组A,B,可以在两个数组选择任意多个数,代价为选择的数的数目,得到的奖励为在数组A和数组B中选择的数的两个总和较小的那个,求能得到的最大收益思路:1.先给两个数组分别由大到小排序后求前缀和,不难得出在数组A中选择i个数,数组B中选择j个数时,最大收益为:m......
  • android: workaround for slow ‘building workspace’ problem in eclipse
    Whiledevelopingforandroidoneclipse3.6ihadtheproblemthateachtimeisavedafile,eclipseblockedmeseveralsecondswith‘buildingworkspace…’.Similartothese:stackoverflow–android-compilation-is-slow-using-eclipsestackoverflow–android-......
  • [CEOI2017] Mousetrap
    100黑祭。首先以终点为根。先考虑简单一点的情况:如果起点终点相邻,那么方案一定是让老鼠先走到一个叶子节点,然后断掉该节点到根路径上其它的分支。于是我们令\(f_i\)表示从\(i\)开始走到\(i\)子树里的一个叶节点再返回所需的最小代价,每次dp从儿子里的次大值转移即可。考虑......