318016 - 拆迁队

题解bymod998244353

可能更好的体验

设f[i]表示前i个房子中，保留i号房子时能保留最多几个旧房子

g[i]表示前i个房子中，保留i号房子，保留旧房子最多时，最小的代价

转移方程为：

f[i]=\max(f[j])+1,0\leq j < i,a[i]-a[j]\geq i-j

g[i]=\min(g[j]+a[j]\times (i-j-1)+\dfrac{(i-j)(i-j-1)}{2})+a[i]+b[i],0\leq j < i,f[i]=f[j]+1,a[i]-a[j]\geq i-j

显然是O(n^2)的，要优化。

a[i]-a[j]\geq i-j \Leftrightarrow a[i]-i\geq a[j]-j

于是令c[i]=a[i]-i，转移方程改为

f[i]=\max(f[j])+1,0\leq j < i,c[i]\geq c[j]

这个可以用O(n\log n)的cdq分治维护，之后考虑优化g[i]。

g[i]=\min(g[j]+a[j]\times (i-j-1)+\dfrac{(i-j)(i-j-1)}{2})+a[i]+b[i]

=\min(g[j]+(a[j]-j)\times i+\dfrac{i(i-1)}{2}+\dfrac{j(j+1)}{2}-a[j]\times j-a[j])+a[i]+b[i]

=\min(c[j]\times i+g[j]+\dfrac{j(j+1)}{2}-a[j]\times j-a[j])+a[i]+b[i]+\dfrac{i(i-1)}{2}(0\leq j < i,f[i]=f[j]+1,c[i]\geq c[j])

令d[i]=\dfrac{i(i+1)}{2}-a[i]\times i-a[i],则

g[i]=\min(c[j]\times i+g[j]+d[j])+a[i]+b[i]+\dfrac{i(i-1)}{2}(0\leq j < i,f[i]=f[j]+1,c[i]\geq c[j])

之后考虑转成斜率式：

假设j,j'都是i的决策点，且j优于j'，c[j'] < c[j]那么有

c[j]\times i+g[j]+d[j]\leq c[j']\times i+g[j']+d[j']

即-i\geq\frac{(g[j]+d[j])-(g[j']+d[j'])}{(c[j]-c[j'])}

用k[j,j']表示\frac{(g[j]+d[j])-(g[j']+d[j'])}{(c[j]-c[j'])}，可以发现它是(c[j],g[j]+d[j])与(c[j'],g[j']+d[j'])的斜率。

当c[j_1] < c[j_2] < c[j_3],k[j_1,j_2] > k[j_2,j_3]时：

1. 当k[j_1,j_2]>-i时，j_1优于j_2
2. 当k[j_1,j_2]\leq -i时，k[j_2,j_3] < -i，j_3优于j_2

所以当c[j_1] < c[j_2] < c[j_3],k[j_1,j_2]> k[j_2,j_3]时可以把j_2删去

这个转移有一个c[i]\geq c[j],f[i]=f[j]+1的条件，所以我们可以考虑用cdq分治维护这个转移方程，大致过程如下：

对于[l,r]：递归[l,mid]，让[l,mid]对[mid+1,r]的转移，递归[mid+1,r]

转移中，用vector存下决策点的点集（即[l,mid]中没有被上面的式子排除的点），转移的时候可以使用三分找最优决策点。

具体过程在代码中有注释，时间复杂度O(n\log^2n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100005;
int tmp[MAXN],n,f[MAXN],a[MAXN],b[MAXN],c[MAXN];
ll d[MAXN],g[MAXN];
struct node {//储存点或者斜率的结构体
    int x;
    ll y;
    node(int a=0,ll b=0) {
        x=a,y=b;
    }
    bool operator>(const node b) const {//比较斜率
        return x*b.y<b.x*y;
    }
};
vector<node>v;
node Slope(node a,node b) {//斜率
    return node(a.x-b.x,a.y-b.y);
}
bool cmp(int x,int y) {
    return c[x]^c[y]?c[x]<c[y]:x<y;
}
void cdq(int l,int r) {
    if(l>=r)return;
    const int mid=l+r>>1;
    cdq(l,mid);//先递归
    int m=0,mx=-1;
    for(int i=l; i<=r; ++i)tmp[++m]=i;
    sort(tmp+1,tmp+m+1,cmp);//把每个点按照f[i]升序排序
    for(int j=1,i; j<=m; ++j) {
        i=tmp[j];
        if(i<=mid) {//对于每个决策点
            if(f[i]<mx||(i&&!f[i]))continue;//无法保留的跳过
            if(f[i]>mx) {//如果转移的f[i]不一样，就把之前的全部删去
                mx=f[i];
                v.clear();
            }
            node p(c[i],d[i]+g[i]);
            while(v.size()>=2&&Slope(v[v.size()-1],v[v.size()-2])>Slope(p,v[v.size()-1]))v.pop_back();//按照前面的斜率式删除点
            v.push_back(p);
        } else {//对于每个被转移的点
            if(f[i]<mx+1) {//如果f[i]有更优值，则前面的转移无效
                f[i]=mx+1;
                g[i]=5e16;
            } else if(f[i]>mx+1) {//不是这个值，就不转移它
                continue;
            }
            int L=0,R=v.size()-1,mm=0,mmm=0;
            while(L+2<R) {//由于维护的是下凸包，可以三分确定最优决策点范围
                mm=L+(R-L+1)/3;
                mmm=R-(R-L+1)/3;
                if(v[mm].x*1ll*i+v[mm].y<=v[mmm].x*1ll*i+v[mmm].y)R=mmm;
                else L=mm;
            }
            for(; L<=R; ++L)//更新答案
                g[i]=min(g[i],v[L].x*1ll*i+v[L].y+i*1ll*(i-1)/2+a[i]+b[i]);
        }
    }
    return cdq(mid+1,r);
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) {
        scanf("%d",&a[i]);
        c[i]=a[i]-i;//算出c[i]
    }
    for(int i=1; i<=n; ++i) {
        scanf("%d",&b[i]);
        g[i]=5e16;
        d[i]=i*(i+1ll)/2-a[i]*1ll*i-a[i];//算出d[i]
    }
    cdq(0,n);
    int ans=0;
    ll res=0;
    for(int i=1; i<=n; ++i)//算答案
        if(f[i]>ans)
            ans=f[i],res=g[i]+(n-i)*(n-i+1ll)/2+(n-i)*1ll*a[i];
        else if(f[i]==ans)
            res=min(res,g[i]+(n-i)*(n-i+1ll)/2+(n-i)*1ll*a[i]);
    printf("%d %lld\n",ans,res);
    return 0;
}