C++14(g++5.4) 解法, 执行用时: 1405ms, 内存消耗: 2644K, 提交时间: 2019-04-20 09:45:05
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
int x = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 70007;
const LL inf = 1e13;
int n, sz, m;
int a[N], bl[N];
LL f[N];
LL l[300][300], mi[300], a1[300];
int a2[300], L[300], R[300], p[300];
#define stk l[B]
void upd(int B) {
while(p[B] > 1 && a2[B] * (stk[p[B]] - stk[p[B] - 1]) >= f[stk[p[B] - 1]] - f[stk[p[B]]]) --p[B];
mi[B] = a1[B] + stk[p[B]] * a2[B] + f[stk[p[B]]];
}
void rebuild(int B) {
rep(i, L[B], R[B]) f[i] += a1[B] + (LL) a2[B] * i;
a1[B] = a2[B] = p[B] = 0;
int &tp = p[B];
rep(i, L[B], R[B]) {
while(tp > 1 && (f[stk[tp - 1]] - f[i]) * (stk[tp] - stk[tp - 1]) >= (f[stk[tp - 1]] - f[stk[tp]]) * (i - stk[tp - 1])) --tp;
stk[++tp] = i;
}
upd(B);
}
#undef stk
void add1(int l, int ed, LL v) {
for(int B, r; l <= ed; l = r + 1) {
B = bl[l], r = min(ed, R[B]);
if(l == L[B] && r == R[B]) a1[B] += v, mi[B] += v;
else {
rep(i, l, r) f[i] += v;
rebuild(B);
}
}
}
void add2(int l, int ed) {
for(int B, r; l <= ed; l = r + 1) {
B = bl[l], r = min(ed, R[B]);
if(l == L[B] && r == R[B]) a2[B] ++, upd(B);
else {
rep(i, l, r) f[i] += i;
rebuild(B);
}
}
}
LL query(int l, int ed) {
LL res = inf;
for(int B, r; l <= ed; l = r + 1) {
B = bl[l], r = min(ed, R[B]);
if(l == L[B] && r == R[B]) Min(res, mi[B]);
else {
rebuild(B);
rep(i, l, r) Min(res, f[i]);
}
}
return res;
}
void make(int p, LL v) {
f[p] = -a1[bl[p]] - (LL) a2[bl[p]] * p + v;
rebuild(bl[p]);
}
int main() {
n = gi(), sz = (int)sqrt(n);
fill(mi, mi + 300, inf);
fill(f, f + N, inf);
rep(i, 1, n) a[i] = gi();
rep(i, 0, n) bl[i] = i / sz;
rep(i, 0, bl[n]) L[i] = i * sz, R[i] = min(n, (i + 1) * sz - 1), rebuild(i);//
make(0, 0);
for(int i = 1, mx = 0; i <= n; ++i) {
make(a[i], query(0, a[i]) + a[i]);
add1(0, a[i] - 1, max(mx, a[i]));
add2(a[i] + 1, mx);
Max(mx, a[i]);
}
printf("%lld\n", query(0, n));
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 20ms, 内存消耗: 744K, 提交时间: 2019-04-19 11:47:32
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 50010;
int a[maxn], b[maxn], tp[2];
pair<int, long long> st[2][maxn];
int main(){
int n; scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= n; ++i) b[i] = a[i];
sort(b + 1, b + 1 + n);
int m = unique(b + 1, b + 1 + n) - (b + 1);
for(int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
int mx= 0;
st[0][++tp[0]] = pair<int, long long>(0, 0ll);
for(int i = 1; i <= n; ++i){
if(mx < b[a[i]]) mx = b[a[i]];
while(tp[0] && st[0][tp[0]].first >= a[i]){
st[1][++tp[1]] = st[0][tp[0]];
--tp[0];
}
st[1][++tp[1]] = pair<int, long long>(a[i], st[0][tp[0]].second);
for(int j = 1; j <= tp[0]; ++j) st[0][j].second += mx;
while(tp[1]){
st[1][tp[1]].second += b[st[1][tp[1]].first];
if(st[1][tp[1]].second < st[0][tp[0]].second)
st[0][++tp[0]] = st[1][tp[1]];
--tp[1];
}
}
printf("%lld\n", st[0][tp[0]].second);
return 0;
}
表示从上往下数第i张纸牌上面的数字。