【BZOJ1597】【Usaco2008 Mar】土地购买 斜率优化DP
wangyuchen
2018-03-18 20:16:56
## 题目：
[题目在这里](http://www.lydsy.com/JudgeOnline/problem.php?id=1597)
## 思路与做法:
这题如果想要直接dp的话不太好处理。
不过， 我们发现如果$a[i].x>=a[j].x$且$a[i].y>=a[j].y$ $($a是输入的数组，x为长，y为宽$)$， j是没用的， 可以直接dp
容易得出状态转移方程为：
$f_i = min \{f_j + x_i * y_{j+1} \}$
可以用斜率优化DP
推导过程：
$f_j + x_i * y_{j+1} < f_k + x_i * y_{k+1}$
$f_j - f_k < x_i*y_{k+1} - x_i*y_{j+1}$
${f_j - _k \over y_{k+1} - y_{j+1}} < x_i$
## 代码：
```cp
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 50010;
struct Data
{ int x, y;
bool operator < (const Data &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); }
} a[N];
vector<int> x, y;
int Q[N], hd, tl;
long long f[N];
inline double calc(int j, int k) { return (double)(f[j]-f[k]) / (double)(y[k+1]-y[j+1]); }
int main()
{ int n;
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d %d", &a[i].x, &a[i].y);
sort(a+1, a+1+n);
x.push_back(0);
y.push_back(0);
for(int i=1; i<=n; i++)
{ while(x.size() > 1 && y.size() > 1 && y.back() <= a[i].y)
x.pop_back(), y.pop_back();
x.push_back(a[i].x);
y.push_back(a[i].y);
}
Q[hd = 0] = 0;
tl = 1;
for(int i=1; i<x.size(); i++)
{ while(hd < tl-1 && calc(Q[hd+1], Q[hd]) <= x[i]) hd++;
f[i] = f[Q[hd]] + (long long)y[Q[hd]+1] * (long long)x[i];
while(hd < tl-1 && calc(i, Q[tl-1]) <= calc(Q[tl-1], Q[tl-2])) tl--;
Q[tl++] = i;
}
printf("%lld\n", f[x.size()-1]);
return 0;
}
```