北京做网站比较好的,网站开发工作,网络设计有哪些,用什么技术做网站正题
题目链接:https://www.luogu.com.cn/problem/P3195 题目大意 nnn个物品#xff0c;分成若干段#xff0c;每一段的长度为j−i∑ilrCkj-i\sum_{il}^rC_kj−i∑ilrCk#xff0c;打包价格为(长度−L)2(长度-L)^2(长度−L)2
求最小价格和。 解题思路 si∑j1iCjs_i\su…正题
题目链接:https://www.luogu.com.cn/problem/P3195 题目大意
nnn个物品分成若干段每一段的长度为j−i∑ilrCkj-i\sum_{il}^rC_kj−i∑ilrCk打包价格为(长度−L)2(长度-L)^2(长度−L)2
求最小价格和。 解题思路
si∑j1iCjs_i\sum_{j1}^iC_jsi∑j1iCj 设fif_ifi表示iii前面的都打包完了有 fifj(si−sji−j−1−L)2f_if_j(s_i-s_ji-j-1-L)^2fifj(si−sji−j−1−L)2 fifj(sii−sj−j−1−L)2f_if_j(s_ii-s_j-j-1-L)^2fifj(sii−sj−j−1−L)2 然后dpdpdp可以做到O(n2)O(n^2)O(n2)因为有平方考虑斜率优化 定义aisii,bisjj1La_is_ii,b_is_jj1Laisii,bisjj1L 有 fifj(ai−bj)2f_if_{j}(a_i-b_j)^2fifj(ai−bj)2 fifjai2−2aibjbj2f_if_ja_i^2-2a_ib_jb_j^2fifjai2−2aibjbj2 2aibjfi−ai2fjbj22a_ib_jf_i-a_i^2f_jb_j^22aibjfi−ai2fjbj2
对于每一个jjj表示一个点(bj,fjbj2)(b_j,f_jb_j^2)(bj,fjbj2)后文中称之为决策点
考虑如何使fif_ifi最小因为ai2a_{i}^2ai2是定值即让fi−ai2f_{i}-a_{i}^2fi−ai2最小那么问题就变为了一条y2aixky2a_ixky2aixk的直线要求经过某个决策点使得kkk最小。
那么显然可能的点一定是一个下凸壳(相邻的点斜率单调上升)而因为2ai2a_i2ai这个斜率也是单调上升的我们可以知道答案就是第一个决策点满足与下一个决策点的斜率≥2ai\geq 2a_i≥2ai。
那么我们维护一个单调队列即可。
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define pow2(x) ((x)*(x))
using namespace std;
const int N5e410;
struct node{double x,y;int num;
}q[N];
int n,head,tail,L;
double s[N],a[N],b[N],f[N];
double slope(node x,node y)
{return ((y.y-x.y)/(y.x-x.x));}
int main()
{scanf(%d%d,n,L);for(int i1;in;i){scanf(%lf,s[i]);s[i]s[i-1];a[i]s[i]i;b[i]s[i]iL1;}b[0]L1;headtail1;q[1](node){b[0],b[0]*b[0],0};for(int i1;in;i){while(headtailslope(q[head],q[head1])2*a[i])head;int pq[head].num;f[i]f[p]pow2(a[i]-b[p]);node w(node){b[i],f[i]b[i]*b[i],i};while(headtailslope(w,q[tail-1])slope(q[tail-1],q[tail]))tail--;q[tail]w;}printf(%.0lf,f[n]);
}
