USACO08MAR Land Acquisition

斜率优化

# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# include <algorithm>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll; IL ll Read(){
RG char c = getchar(); RG ll x = 0, z = 1;
for(; c > '9' || c < '0'; c = getchar()) z = c == '-' ? -1 : 1;;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
return x * z;
} const int MAXN(50010);
const ll INF(1e18);
int n, len[MAXN], wid[MAXN], id[MAXN], land[MAXN], cnt, Q[MAXN], tail, head;
ll f[MAXN]; IL bool Cmp(RG int a, RG int b){
return len[a] < len[b] || (len[a] == len[b] && wid[a] < wid[b]);
} IL double Calc(RG int i, RG int j){
return 1.0 * (f[j] - f[i]) / (wid[land[i + 1]] - wid[land[j + 1]]);
} int main(){
n = Read();
for(RG int i = 1; i <= n; i++)
len[i] = Read(), wid[i] = Read(), id[i] = i;
sort(id + 1, id + n + 1, Cmp);
for(RG int i = 1; i <= n; i++){
while(cnt && wid[land[cnt]] <= wid[id[i]]) cnt--;
land[++cnt] = id[i];
}
//鍦熷湴鐨刲ength渚濇閫掑锛屽湡鍦扮殑width渚濇閫掑噺
for(RG int i = 1; i <= cnt; i++){
while(head < tail && Calc(Q[head], Q[head + 1]) < len[land[i]]) head++;
f[i] = f[Q[head]] + 1LL * len[land[i]] * wid[land[Q[head] + 1]];
while(head < tail && Calc(Q[tail - 1], Q[tail]) >= Calc(Q[tail], i)) tail--;
Q[++tail] = i;
}
printf("%lld\n", f[cnt]);
return 0;
}
上一篇:C++设计模式实现--组合(Composite)模式


下一篇:x11vnc