企业官网建设流程全解析

肥料网站建设 中企动力,txt网站推荐,广州网站建设怎么做,南京中石化第五建设有限公司P2900 [USACO08MAR] Land Acquisition G 题目描述 Farmer John 准备扩大他的农场#xff0c;眼前他正在考虑购买 NNN 块长方形的土地。 如果 FJ 单买一块土地#xff0c;价格就是土地的面积。但他可以选择并购一组土地#xff0c;并购的价格为这些土地中最大的长乘以最大的宽…P2900 [USACO08MAR] Land Acquisition G题目描述Farmer John 准备扩大他的农场眼前他正在考虑购买NNN块长方形的土地。如果 FJ 单买一块土地价格就是土地的面积。但他可以选择并购一组土地并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块3×53 \times 53×5和一块5×35 \times 35×3的土地他只需要支付5×5255 \times 5255×525元 比单买合算。FJ 希望买下所有的土地。他发现将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸请你帮助他计算购买所有土地所需的最小费用。输入格式第一行一个整数NNN1≤N≤5×1041 \leq N \leq 5 \times 10^41≤N≤5×104。接下来NNN行每行两个整数wiw_iwi​和lil_ili​代表第iii块土地的长和宽。保证土地的长和宽不超过10610^6106。输出格式输出买下所有土地的最小费用。输入输出样例 #1输入 #14 100 1 15 15 20 5 1 100输出 #1500说明/提示将所有土地分为三组第一块土地为第一组花费100×1100100 \times 1100100×1100第二三块土地为第二组花费20×1530020 \times 1530020×15300第四块土地为第三组花费1×1001001 \times 1001001×100100总花费为500500500可以证明不存在更优的方案。思路动态规划 DP斜率优化代码见下#includebits/stdc.husingnamespacestd;longlongn,m0,ma0,f[50004];structone{longlongx,y;}a[50004],b[50004];boolcmp(one a1,one b1){if(a1.x!b1.x){returna1.xb1.x;}else{returna1.yb1.y;}}intmain(){cinn;for(inti1;in;i){cina[i].xa[i].y;}sort(a1,an1,cmp);for(inti1;in;i){if(maa[i].y-1){b[m]a[i];maa[i].y;}}memset(f,62,sizeof(f));f[0]0;for(inti1;im;i){for(intjmax(0,i-1-30000);ji-1;j){if(f[j]b[j1].x*b[i].yf[i]){f[i]f[j]b[j1].x*b[i].y;}//f[i]min(f[i],f[j]b[j1].x*b[i].y);}}coutf[m]endl;return0;}