思路:先把没有用的土地去掉,然后按照x轴排序,容易得到dp转移方程

dp[ i ] = min{ dp[ j ] + b[ j + 1 ] * a[ i ] }    0 <= j < i

典型的斜率优化。

#include<bits/stdc++.h>
#define LL long long
#define ll long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define y1 skldjfskldjg
#define y2 skldfjsklejg using namespace std; const int N = 2e5 + ;
const int M = 1e7 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +; struct node {
LL x, y;
node(LL x = , LL y = ) {
this->x = x;
this->y = y;
}
bool operator < (const node &rhs) const {
if(x == rhs.x) return y < rhs.y;
return x < rhs.x;
}
} a[N]; int n, tot, head, rear, stk[N];
LL dp[N]; bool check1(int id1, int id2, LL c) {
return dp[id2] - dp[id1] <= c * (a[id1 + ].y - a[id2 + ].y);
} bool check2(int id1, int id2, int id3, int id4) {
return (dp[id4] - dp[id3]) * (a[id1 + ].y - a[id2 + ].y) <= (dp[id2] - dp[id1]) * (a[id3 + ].y - a[id4 + ].y);
} int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%lld%lld", &a[i].x, &a[i].y);
}
sort(a + , a + + n);
tot = ;
for(int i = ; i <= n; i++) {
while(tot && a[i].y >= a[tot].y) tot--;
a[++tot] = a[i];
}
n = tot; dp[] = ;
stk[++rear] = ; for(int i = ; i <= n; i++) {
while(rear > head && check1(stk[head], stk[head + ], a[i].x)) head++;
int id = stk[head];
dp[i] = dp[id] + a[id + ].y * a[i].x;
while(rear > head && check2(stk[rear - ], stk[rear], stk[rear], i)) rear--;
stk[++rear] = i;
}
printf("%lld\n", dp[n]);
return ;
} /*
*/

最新文章

  1. 制作鼠标移动到div上面显示弹出框
  2. 动态添加PopupWindow
  3. BZOJ4380 : [POI2015]Myjnie
  4. c#重载和重写及运用
  5. DateTime.IsLeapYear 方法判断是否是闰年,DaysInMonth判断一个月有几天,Addday取得前一天的日期GetYesterDay
  6. mysql数据库学习(一)--基础
  7. Functor仿函数
  8. java第十三次作业
  9. HDU4508--完全背包
  10. 20160220.CCPP体系详解(0030天)
  11. LoadRunner学习笔记(三)
  12. 【原创】JAVA面试解析(有赞一面)
  13. HDU 2149 巴什博奕
  14. Painter&#39;s Problem (高斯消元)
  15. NodeJS旅程 : express - nodejs MVC 中的王牌
  16. linux内置软件安装命令
  17. linux_kernel_uaf漏洞利用实战
  18. verilog实现VGA显示方块屏幕保护
  19. (转) linux下vim和bash配置文件
  20. Sublime Text 3常用插件安装

热门文章

  1. python 栈和队列
  2. 用Apache Spark和TensorFlow进行的深度学习
  3. Android UI开发第二十四篇——Action Bar
  4. 使用localhost调试本地代码,setcookie无效
  5. 策略模式 C#
  6. Linux 命令行生成密码的 10 种方式
  7. 【洛谷 P3187】 [HNOI2007]最小矩形覆盖 (二维凸包,旋转卡壳)
  8. 【洛谷 P3899】 [湖南集训]谈笑风生 (主席树)
  9. jq 浏览器窗口大小发生变化时
  10. YUV颜色编码解析(转)