苏州 规划建设局网站,网页设计师培训费用图,建设网站 系统占用空间,做兼职的设计网站有哪些工作内容玩具装箱
金牌导航 决策单调性优化DP-1
题目大意
给出若干个物品#xff0c;把iii到jjj个物品装在一起的长度lj−i∑kijaklj-i\sum_{ki}^{j}a_klj−i∑kijak#xff08;物品必须是连续的#xff09;#xff0c;其代价为(lL)2(l L)^2(lL)2#xff08;L为给出的常数…玩具装箱
金牌导航 决策单调性优化DP-1
题目大意
给出若干个物品把iii到jjj个物品装在一起的长度lj−i∑kijaklj-i\sum_{ki}^{j}a_klj−i∑kijak物品必须是连续的其代价为(lL)2(l L)^2(lL)2L为给出的常数问把所有物品装起来的最小代价
输入样例
5 4
3
4
2
1
4输出样例
1样例解释
按3,4,21,4分配 代价为10001
数据范围
1⩽N⩽5×104,1⩽L,ai⩽1071\leqslant N \leqslant 5\times 10^4,1\leqslant L,a_i\leqslant 10^71⩽N⩽5×104,1⩽L,ai⩽107
解题思路
设f_i为前i个物品装完的最小代价 那么有 fiminj1i−1(fj(l−L)2)f_imin_{j1}^{i-1}(f_j (l-L)^2)fiminj1i−1(fj(l−L)2) 把代入四边形不等式然后暴力拆开可以证明其满足决策单调性 然后代入决策单调性的模板即可
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 50010
using namespace std;
ll n, L, l, r, mid, top, a[N], f[N], d[N], lt[N];
ll g(ll x, ll y)
{return f[x] (y - x - 1 a[y] - a[x] - L) * (y - x - 1 a[y] - a[x] - L);
}
ll find(ll x)
{ll l 1, r top;while(l r){ll mid (l r 1) 1;if (x lt[mid]) r mid - 1;else l mid;}return d[l];
}
int main()
{scanf(%lld%lld, n, L);for (ll i 1; i n; i){scanf(%lld, a[i]);a[i] a[i - 1]; }lt[top] 1;d[top] 0;for (ll i 1; i n; i){f[i] g(find(i), i);while(top g(i, lt[top]) g(d[top], lt[top])) top--;l lt[top];r n;while (l r){mid (l r) 1;if (g(i, mid) g(d[top], mid)) r mid;else l mid 1;}if (g(i, l) g(d[top], l)) continue;d[top] i;lt[top] l;}printf(%lld, f[n]);return 0;
}注本题可以用斜率优化进行计算但这里不进行讲解
