bzoj1597 斜率优化dp
2024-09-04 15:54:32
思路:先把没有用的土地去掉,然后按照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 ;
} /*
*/
最新文章
- 制作鼠标移动到div上面显示弹出框
- 动态添加PopupWindow
- BZOJ4380 : [POI2015]Myjnie
- c#重载和重写及运用
- DateTime.IsLeapYear 方法判断是否是闰年,DaysInMonth判断一个月有几天,Addday取得前一天的日期GetYesterDay
- mysql数据库学习(一)--基础
- Functor仿函数
- java第十三次作业
- HDU4508--完全背包
- 20160220.CCPP体系详解(0030天)
- LoadRunner学习笔记(三)
- 【原创】JAVA面试解析(有赞一面)
- HDU 2149 巴什博奕
- Painter&#39;s Problem (高斯消元)
- NodeJS旅程 : express - nodejs MVC 中的王牌
- linux内置软件安装命令
- linux_kernel_uaf漏洞利用实战
- verilog实现VGA显示方块屏幕保护
- (转) linux下vim和bash配置文件
- Sublime Text 3常用插件安装