laekov

大概也不是很难。毕竟只有做水题的份。

就把原来的土地按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]);

}