「BZOJ3437」小P的牧场

Description

小P在MC里有nn个牧场,自西向东呈一字形排列(自西向东用1n1\cdots n编号),于是他就烦恼了:为了控制这nn个牧场,他需要在某些牧场上面建立控制站,每个牧场上只能建立一个控制站,每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场(它西边第一个控制站所在的牧场不被控制)(如果它西边不存在控制站,那么它控制西边所有的牧场),每个牧场被控制都需要一定的花费(毕竟在控制站到牧场间修建道路是需要资源的嘛~),而且该花费等于它到控制它的控制站之间的牧场数目(不包括自身,但包括控制站所在牧场)乘上该牧场的放养量,在第ii个牧场建立控制站的花费是aia_i,每个牧场ii的放养量是bib_i,理所当然,小P需要总花费最小,但是小P的智商有点不够用了,所以这个最小总花费就由你来算出啦。

Input

第一行一个整数 nn 表示牧场数目
第二行包括nn个整数,第ii个整数表示aia_i
第三行包括$$n个整数,第ii个整数表示bib_i

Output

只有一行,包括一个整数,表示最小花费

Sample Input

1
2
3
4
2 4 2 4
3 1 4 2

Sample Output

1
9

HINT

1n1000000,0<ai,bi100001\leq n\leq 1000000, 0 < a_i ,b_i \leq 10000

Solution

暴力

先翻转序列。
fif_i表示在ii建立控制站得到的最小花费。
显然初始状态必须是f1=i=2nbi(i1)+a1f_1=\sum_{i=2}^nb_i(i-1)+a_1
fi=min{fj(ij)×(snsi)+ai}f_i=\min\{f_j-(i-j)\times (s_n-s_i) + a_i\}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e6 + 66;
ll a[N], f[N], b[N], s[N];
int n;
int pre[N];
int main() {
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) b[i] = read();
reverse(b+1,b+1+n);
reverse(a+1,a+1+n);
f[1] = a[1];
for(int i = 1; i <= n; ++i) f[1] += (i - 1) * b[i], s[i] = s[i - 1] + b[i];
for(int i = 2; i <= n; ++i) {
f[i] = 1e18;
for(int j = 1; j < i; ++j) {
ll val = f[j] - (i - j) * (s[n] - s[i - 1]) + a[i];
if(val < f[i]) pre[i] = j, f[i] = val;
}
}
ll ans = 1e18;
for(int i = 1; i <= n; ++i)
ans = min(ans, f[i]);
writeln(ans);
return 0;
}

std

斜率优化一波!为了方便就不翻转序列了,kk递减,维护下凸壳即可。从nn11做,相当于斜率kk递增,其他都递增。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e6 + 66;
ll a[N], f[N], b[N], s[N];
int n;
int q[N], h, t;
double slope(int x, int y) {
return (double)(f[y] - f[x]) / (y - x);
}
int main() {
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) b[i] = read();
f[n] = a[n];
for(int i = 1; i <= n; ++i) f[n] += (n - i) * b[i], s[i] = s[i - 1] + b[i];
q[h = t = 1] = n;
for(int i = n - 1; i; --i) {
f[i] = 1e18;
ll S = s[i];
while(h < t && slope(q[h + 1], q[h]) >= S) ++h;
f[i] = f[q[h]] - (q[h] - i) * S + a[i];
while(h < t && slope(q[t], q[t - 1]) <= slope(i, q[t - 1])) --t;
q[++t] = i;
}
ll ans = 1e18;
for(int i = 1; i <= n; ++i)
ans = min(ans, f[i]);
writeln(ans);
return 0;
}