手机微网站怎么制作,闵行18路,公众平台申请,wordpress主题整合前言
然而丝之鸽还是没有出 正题
题目链接:https://www.luogu.com.cn/problem/P6047 题目大意
两个平行的线#xff0c;上面连接着若干条弦#xff0c;第iii条连接上方的xix_ixi个下方的yiy_iyi。 然后每次可以选择一个位置(i,j)(i,j)(i,j)#xff0c;可以切断任何位…前言
然而丝之鸽还是没有出 正题
题目链接:https://www.luogu.com.cn/problem/P6047 题目大意
两个平行的线上面连接着若干条弦第iii条连接上方的xix_ixi个下方的yiy_iyi。 然后每次可以选择一个位置(i,j)(i,j)(i,j)可以切断任何位于位置(u,v)(u,v)(u,v)的弦仅当满足条件(ui,vj)(ui,vj)(ui,vj)消耗代价为ai∗bja_i*b_jai∗bj。
求切断所有线的最小代价。 解题思路
如果我们将下面那条线翻转过来我们就有条件(ui,vj)(ui,vj)(ui,vj)我们将弦看成坐标的话我们可以发现其实就是每次选择一个点然后将右下角的点都去掉。
所以就有以下优化
如果一个弦代表的点在其他弦代表点的右下角那么该点不影响结果。可以去掉如果一个点的代价比他右上角的其中一个点的代价高那么必定选那个点更优。所以我们可以对于aaa和bbb都取一个前缀minminmin
做完以下优化后对于弦我们可以求到xxx递增yyy递减的序列。转换到之后就是axa_xax递减byb_yby递增的序列可以进行dpdpdp。 fimin{fj,fjaxj1byi}f_imin\{f_j,f_ja_{x_j1}b_{y_i}\}fimin{fj,fjaxj1byi} 考虑斜率优化 fifjaxj1byif_if_ja_{x_j1}b_{y_i}fifjaxj1byi 转换成函数 fj−axj1byifif_j-a_{x_j1}b_{y_i}f_ifj−axj1byifi
斜率为−byi-b_{y_i}−byi要求截距最小维护下凸壳斜率递增。
然后因为都是单调的可以用单调队列维护。 codecodecode
#includecstdio
#includealgorithm
#define ll long long
using namespace std;
const ll N3e510;
struct node{ll x,y;
}a[N];
ll n,m,q[N];
double x[N],y[N],f[N];
bool cmp(node x,node y)
{return (x.xy.x)?(x.yy.y):(x.xy.x);}
double slope(ll i,ll j){if(a[i1].xa[j1].x)return 1e18;return (f[i]-f[j])/(a[j1].x-a[i1].x);
}
int main()
{scanf(%lld%lld,n,m);for(ll i1;in;i)scanf(%lf,x[i]);for(ll in;i1;i--)scanf(%lf,y[i]);x[0]y[0]1e18;for(ll i1;in;i)x[i]min(x[i],x[i-1]),y[i]min(y[i],y[i-1]);for(ll i1;im;i)scanf(%lld%lld,a[i].x,a[i].y),a[i].yn-a[i].y1;sort(a1,a1m,cmp);ll p0;a[0].y2147483647/3;for(ll i1;im;i)if(a[i].ya[p].y)a[p]a[i];mp;ll l1,r1;for(ll i1;im;i)a[i].xx[a[i].x-1],a[i].yy[a[i].y-1];for(ll i1;im;i){while(lrslope(q[l],q[l1])a[i].y)l;ll posq[l];f[i]f[pos]a[pos1].x*a[i].y;while(lrslope(q[r-1],q[r])slope(q[r],i))r--;q[r]i;}printf(%.0lf,f[m]);
}
