大概也不是很难。毕竟只有做水题的份。
就把原来的土地按x排个序，把能合并的合并，变成一个x单增y单减的序列。
然后就是dp。f[i] = min(f[j] + y[j+1]*x[i])，可以单调的斜率优化。
符号比较郁闷还搞错了好几次。
所以说我太弱了啊怎么办啊。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long qw;
typedef long double exf;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define _l (qw)
#define _f (exf)
struct field {
int x, y;
};
inline bool cmpField(const field& a, const field& b) {
return (a. x < b. x) || (a. x == b. x && a. y < b. y);
}
const int maxn = 50009;
int n, t;
int q[maxn];
qw f[maxn];
field o[maxn], a[maxn];
#define getK(_x_,_y_) ((_f f[_y_]-f[_x_])/(_f a[_x_+1].y-a[_y_+1].y))
void dp() {
int hd = 0, tl = 1;
a[0]. x = 0;
a[0]. y = 0;
f[0] = 0;
q[hd] = 0;
for (int i = 1; i <= t; ++ i) {
while (hd + 1 < tl && getK(q[hd], q[hd + 1]) < a[i]. x)
++ hd;
f[i] = f[q[hd]] + _l a[q[hd] + 1]. y * a[i]. x;
if (i == t)
break;
while (hd + 1 < tl && getK(q[tl - 2], q[tl - 1]) > getK(q[tl - 2], i))
-- tl;
q[tl ++] = i;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 0; i < n; ++ i)
scanf("%d%d", &o[i]. x, &o[i]. y);
sort(o, o + n, cmpField);
t = 1;
a[1] = o[0];
for (int i = 1; i < n; ++ i) {
while (t && o[i]. y > a[t]. y)
-- t;
if (!t || o[i]. x > a[t]. x)
a[++ t] = o[i];
}
dp();
printf(lld "\n", f[t]);
}