高校网站建设前景,760关键词排名查询,网站开发的基本流程 岗位及职责,wordpress设计类网站正题
题目链接:https://www.luogu.com.cn/problem/P2900 题目大意 nnn块hi∗wih_i*w_ihi∗wi的土地#xff0c;购买一组土地需要max(h)∗max(w)max(h)*max(w)max(h)∗max(w)#xff0c;求购买所有土地的最小费用。 解题思路
首先如果hhh和www都小于另一块土地显然是不需…正题
题目链接:https://www.luogu.com.cn/problem/P2900 题目大意
nnn块hi∗wih_i*w_ihi∗wi的土地购买一组土地需要max(h)∗max(w)max(h)*max(w)max(h)∗max(w)求购买所有土地的最小费用。 解题思路
首先如果hhh和www都小于另一块土地显然是不需要的去掉后我们可以得到一个hhh递减www递增的序列 设fif_ifi表示并购到第iii个时最小费用有转移fimin{fjhj1∗wi}f_imin\{f_jh_{j1}*w_i\}fimin{fjhj1∗wi} 比较两个决策fjhj1∗wifkhk1∗wif_jh_{j1}*w_if_kh_{k1}*w_ifjhj1∗wifkhk1∗wi fj−fkwi∗(hk1−hj1)f_j-f_kw_i*(h_{k1}-h_{j1})fj−fkwi∗(hk1−hj1) fj−fkhk1−hj1wi\frac{f_j-f_k}{h_{k1}-h_{j1}}w_ihk1−hj1fj−fkwi
然后斜率优化时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
struct node{ll h,w;
}a[N];
ll n,f[N],q[N];
bool cmp(node x,node y)
{return (x.hy.h)?(x.wy.w):(x.hy.h);}
double slope(ll x,ll y)
{return 1.0*(f[x]-f[y])/(a[y1].h-a[x1].h);}
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld%lld,a[i].h,a[i].w);sort(a1,a1n,cmp);ll p1;for(ll i1;in;i)if(a[i].wa[p].w)a[p]a[i];np;ll l1,r1;q[1]0;for(ll i1;in;i){while(lrslope(q[l],q[l1])a[i].w)l;f[i]f[q[l]]a[q[l]1].h*a[i].w;while(lrslope(q[r-1],q[r])slope(q[r-1],i))--r;q[r]i;}printf(%lld,f[n]);
}
