国际惯例的题面:
我们考虑大力DP。
首先重新定义代价为:1e13*选择数量-(总高度+总补偿)。这样我们只需要一个long long就能维护。
然后重新定义高度为heighti - i，这样我们能选择高度相同的点，同时可以把无论如何也不会被选择的点扔掉(这样他们的高度<0)。
之后就是转移，我们枚举i前面的被选择的点j，我们要满足的东西有:hj<=hi。
考虑我们再次选择一个点会产生怎样的代价，显然最终的答案一定是一个阶梯状的东西，所以我们选择了i之后之后所有点的高度相对于仅选择j都会上升(hi-hj)。
于是我们就可以转移了，fi=max{fj+(hi-hj)*(n-i+1)}(hj<=hi)+cost[i]，cost[i]为单点价值减去选i的补偿代价。于是你可以写对拍用的n^2暴力了。
仔细观察这个转移方程，显然是一个可斜率优化的方程，我们可以把hi当成x，把fi当成j，把(n-i+1)当成a，把1当成b，这样最优答案就是ax+by的形式了。
因为hi不满足单调性，所以我们需要set维护凸包
考虑到我们还有hj<=hi的限制，所以需要再套一层cdq分治......
注意:
cdq分治在排序的时候不能只排单一关键字，需要做双关键字排序，否则会导致一些能更新的东西无法更新。
然后发现你这么写并不能AC，因为常数太大......
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#define debug cout
typedef long long int lli;
using namespace std;
const int maxn=1e5+1e2;
const lli mul = 1e13+1e10; namespace Convex {
int cmp; // 0 compare x , 1 compare slope .
struct Point {
lli x,y;
long double slop;
friend bool operator < (const Point &a,const Point &b) {
if( !cmp ) return a.x != b.x ? a.x < b.x : a.y < b.y;
return a.slop > b.slop;
}
friend Point operator - (const Point &a,const Point &b) {
return (Point){a.x-b.x,a.y-b.y};
}
friend long double operator * (const Point &a,const Point &b) {
return (long double)a.x * b.y - (long double)b.x * a.y;
}
inline lli calc(lli a,lli b) const {
return a * x + b * y;
}
};
set<Point> st; inline void Pop_right(set<Point>::iterator nxt,const Point &p) {
set<Point>::iterator lst;
while() {
nxt = st.lower_bound(p);
lst = nxt , ++nxt;
if( nxt == st.end() ) return;
if( lst->x == p.x ) {
if( p.y > lst->y ) st.erase(lst);
else break;
}
else {
if( (*lst-p) * (*nxt-*lst) < ) return;
st.erase(lst);
}
}
}
inline void Pop_left(set<Point>::iterator prv,const Point &p) {
set<Point>::iterator lst;
prv = st.lower_bound(p) , --prv;
if( prv == st.begin() && prv->x == p.x ) return void(st.erase(prv));
while(prv!=st.begin()) {
prv = st.lower_bound(p) , --prv;
lst = prv , --prv;
if( p.x == lst->x ) {
if( p.y > lst->y ) st.erase(lst);
else break;
continue;
}
else {
if( (*lst-*prv) * (p-*lst) < ) break;
st.erase(lst);
}
}
}
inline bool fail(const Point &p) {
set<Point>::iterator it = st.lower_bound((Point){p.x,,});
if( it != st.end() && it->x == p.x ) {
if( it->y >= p.y ) return ; // p is useless at all .
else return ; // p must be on convex .
}
if( it != st.end() && it != st.begin() ) {
set<Point>::iterator prv = it; --prv;
if( ( p - *prv ) * (*it - p ) > ) return ;
}
return ;
}
inline void insert(const Point &p) {
cmp = ;
if( fail(p) ) return;
set<Point>::iterator prv,nxt,lst=st.lower_bound(p);
if(lst!=st.begin()) Pop_left(--lst,p);
lst=st.lower_bound(p);
if(lst!=st.end()) Pop_right(lst,p);
st.insert(p) , lst = st.find(p);
if(lst!=st.begin()) {
prv = lst , --prv;
Point x = *prv;
x.slop = (long double)( p.y - x.y ) / ( p.x - x.x );
st.erase(prv) , st.insert(x);
}
nxt = lst = st.find(p) , ++nxt;
if(nxt!=st.end()) {
Point x = p , n = *nxt;
x.slop = (long double)( n.y - x.y ) / ( n.x - x.x );
st.erase(lst) , st.insert(x);
} else {
Point x = p;
x.slop = -1e18;
st.erase(lst) , st.insert(x);
}
}
inline lli query(const lli &k) {
cmp = ;
set<Point>::iterator it = st.lower_bound((Point){,,(long double)-k}); // it can't be st.end() if st isn't empty .
if( it==st.end() ) return ;
lli ret = it->calc(k,);
if( it != st.begin() ) {
--it;
ret = max( ret , it->calc(k,) );
}
++it; if( ++it!=st.end() ) ret = max( ret , it->calc(k,) );
return ret;
}
inline void clear() {
st.clear() , cmp = ;
}
} lli ina[maxn],inb[maxn],f[maxn],cst[maxn],ans,add; // f[id] .
bool isl[maxn];
int n; int cmp; // 0 compare height , 1 compare id .
struct Node {
lli hei,id;
friend bool operator < (const Node &a,const Node &b) {
if( cmp ) return a.id != b.id ? a.id < b.id : a.hei < b.hei;
else return a.hei != b.hei ? a.hei < b.hei : a.id < b.id;
}
}ns[maxn]; vector<Node> vec; inline void solve(vector<Node> &vec) {
if( vec.size() <= ) {
if( vec.size() ) f[vec[].id] = max( f[vec[].id] , cst[vec[].id] );
return;
}
vector<Node> vl,vr;
const unsigned mid = vec.size() >> ;
for(unsigned i=;i<mid;i++) vl.push_back(vec[i]);
for(unsigned i=mid;i<vec.size();i++) vr.push_back(vec[i]);
solve(vl);
for(unsigned i=;i<vl.size();i++) isl[vl[i].id] = ;
for(unsigned i=;i<vr.size();i++) isl[vr[i].id] = ;
cmp = , sort(vec.begin(),vec.end()) , Convex::clear();
for(unsigned i=;i<vec.size();i++) {
if( isl[vec[i].id] ) {
Convex::insert((Convex::Point){vec[i].hei,f[vec[i].id],});
} else {
f[vec[i].id] = max( f[vec[i].id] , cst[vec[i].id] + Convex::query(n-vec[i].id+));
}
}
solve(vr);
} int main() {
static lli sel,lst;
scanf("%d",&n) , add = (lli) n * ( n + ) >> ;
for(int i=;i<=n;i++) scanf("%lld",ina+i) , ina[i] -= i;
for(int i=;i<=n;i++) {
scanf("%lld",inb+i);
if( ina[i] >= ) {
cst[i] = mul - inb[i] - ina[i] * ( n - i + ) ,
vec.push_back((Node){ina[i],i});
}
}
cmp = , sort(vec.begin(),vec.end());
solve(vec);
for(int i=;i<=n;i++) ans = max( ans , f[i] );
ans -= add;
sel = ( ans + mul ) / mul;
lst = mul * sel - ans;
printf("%lld %lld\n",sel,lst);
return ;
}
另外这个东西其实不用平衡树维护凸包，如果你外层分治位置，内层分治height的话，height就会有序，这样只需要写一个普通凸包就好了......
在BZOJ上只有这样才能AC......//QAQ
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define debug cout
typedef long long int lli;
typedef long double ldb;
using namespace std;
const int maxn=1e5+1e2;
const lli mul = 1e13 + 1e10; struct Convex {
struct Point {
lli x,y;
friend Point operator - (const Point &a,const Point &b) {
return (Point){a.x-b.x,a.y-b.y};
}
friend ldb operator * (const Point &a,const Point &b) {
return (ldb)a.x*b.y - (ldb)a.y*b.x;
}
friend lli operator ^ (const Point &a,const Point &b) {
return a.x * b.x + a.y * b.y;
}
}ps[maxn];
int top;
inline void push(const Point &p) {
while( top > ) {
if( p.x == ps[top].x && p.y > ps[top].y ) --top;
else if( ( ps[top] - ps[top-] ) * ( p - ps[top] ) > ) --top;
else break;
}
if( top == && p.x == ps[top].x && p.y > ps[top].y ) --top;
if( !top || p.x != ps[top].x ) ps[++top] = p;
}
inline lli query(const Point &p) {
int l = , r = top , lmid , rmid;
while( r > l + ) {
lmid = ( l + l + r ) / , rmid = ( l + r + r ) / ;
if( ( p ^ ps[lmid] ) < ( p ^ ps[rmid] ) ) l = lmid;
else r = rmid;
}
lli ret = ;
for(int i=l;i<=r;i++) ret = max( ret , p ^ ps[i] );
return ret;
}
inline void clear() {
top = ;
}
}con; lli ina[maxn],inb[maxn],f[maxn],cst[maxn],ans,add; // f[id] .
bool isl[maxn];
int n; int cmp; // 0 compare height , 1 compare id .
struct Node {
lli hei,id;
friend bool operator < (const Node &a,const Node &b) {
if( cmp ) return a.id != b.id ? a.id < b.id : a.hei < b.hei;
else return a.hei != b.hei ? a.hei < b.hei : a.id < b.id;
}
}ns[maxn]; vector<Node> vec; inline void solve(vector<Node> &vec) {
if( vec.size() <= ) {
if( vec.size() ) f[vec[].id] = max( f[vec[].id] , cst[vec[].id] );
return;
}
vector<Node> vl,vr;
const unsigned mid = vec.size() >> ;
for(unsigned i=;i<mid;i++) vl.push_back(vec[i]);
for(unsigned i=mid;i<vec.size();i++) vr.push_back(vec[i]);
solve(vl);
for(unsigned i=;i<vl.size();i++) isl[vl[i].id] = ;
for(unsigned i=;i<vr.size();i++) isl[vr[i].id] = ;
cmp = , sort(vec.begin(),vec.end()) , con.clear();
for(unsigned i=;i<vec.size();i++) {
if( isl[vec[i].id] ) {
con.push((Convex::Point){vec[i].hei,f[vec[i].id]});
} else {
f[vec[i].id] = max( f[vec[i].id] , cst[vec[i].id] + con.query((Convex::Point){n-vec[i].id+,}));
}
}
solve(vr);
} int main() {
static lli sel,lst;
scanf("%d",&n) , add = (lli) n * ( n + ) >> ;
for(int i=;i<=n;i++) scanf("%lld",ina+i) , ina[i] -= i;
for(int i=;i<=n;i++) {
scanf("%lld",inb+i);
if( ina[i] >= ) {
cst[i] = mul - inb[i] - ina[i] * ( n - i + ) ,
vec.push_back((Node){ina[i],i});
}
}
cmp = , sort(vec.begin(),vec.end());
solve(vec);
for(int i=;i<=n;i++) ans = max( ans , f[i] );
ans -= add;
sel = ( ans + mul ) / mul;
lst = mul * sel - ans;
printf("%lld %lld\n",sel,lst);
return ;
}