题目大意在第\((i,j)\)个格子修建一个桥墩需要\(a_{i,j}+1\)的花费而且要求\((i,0)\)与\((i,m)\)必须修建桥墩并且桥墩之间的距离不得大于\(d\)。现在需要求见\(k\)个连续的桥，求最小代价。其中\(1\lek\len\le100,3\lem\le2\cdot10,1\led\lem\)。思路因为

视频链接：C121李超树+DPP4655[CEOI2017]BuildingBridges_哔哩哔哩_bilibili   LuoguP4655[CEOI2017]BuildingBridges#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;#definelllonglong#definelsu<<

原题链接：Problem-E-Codeforces题目大意：给一个行为n列为m的河流二维数组，数字代表河流的深度。题目要求连续建造k座桥，桥的定义是从第一列到第m列，每隔d需要按照支架，安装支架的代价是深度+1。问安装最少需要多少代价？思路：单调队列优化dp，dp数组只需要一维，dp[i]的含义是从1到i建

ARC143DBridges巧妙的图论题。思路分析题目，发现很像拆点。由于拆点要设置出入点，这里我们也把\(a_i\)设成入点，把\(a_i+n\)设成出点，再次分析问题。考虑我们把拆的点合并成一个点，对于\((a_i,b_i)\)建边，建出图\(G\)。不难发现，原图是图\(G\)展开后的形态，且只有按照出入

\(HDU4738\)\(Caocao\)'\(s\)\(Bridges\)一、题目描述曹操在长江上建立了一些点，点之间有一些边连着。如果这些点构成的无向图变成了连通图，那么曹操就无敌了。刘备为了防止曹操变得无敌，就打算去摧毁连接曹操的点的桥。但是诸葛亮把所有炸弹都带走了，只留下一枚给刘备。所以刘

小清新斜率优化题。分段问题显然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=

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\)。