Chlience

【题解】BZOJ 2149 拆迁队
Problem给定一个长度为 $n$ 的数列 $a_i$ 你希望把这个数列变成一个严格递增的数列每个位置 $i$...
扫描右侧二维码阅读全文
09
2019/03

【题解】BZOJ 2149 拆迁队

Problem

给定一个长度为 $n$ 的数列 $a_i$
你希望把这个数列变成一个严格递增的数列
每个位置 $i$ 可以它修改为一个新的数,也可以不修改,但这样需要花费 $b_i$
设最终的数列为 $c_i$ ,这个数列需要满足$\forall c_i>0,c_i<c_{i+1}$

总花费为 $\sum_{i=1}^{n} c_i+\sum b$

求最大化不变位置的最小花费

Thought

首先将其转化为非严格递增数列,即 $d[i]=a[i]-i$

设 $g[i]$ 为选择 $i$ 不进行修改的最大长度,可以得到转移:

$$ g[i]=\max\{g[j]\}+1,j<i,d[j]\leq d[i] $$

求出 $g$ 后,我们可以分层求出 $f[i]$,即保留 $i$ 不进行修改的最小花费

$$ f[i]=\min\{f[j]+d[j]*(i-j-1)+\frac{(i+j)(i-j-1)}{2}+a[i]+b[i]\}\\ f[i]=\min\{d[j]*i+f[j]-d[j]*(j+1)-\frac{j(j+1)}{2}\}+\frac{i(i-1)}{2}+a[i]+b[i] $$

其中需要保证 $j<i,d[j]\leq d[i],g[j]+1=g[i]$

发现可以分层进行计算,相邻层之间使用 $CDQ$ 分治计算贡献
并且每个选择的贡献一个和 $i$ 相关的一次函数,那么考虑维护一个凸壳,每次在凸壳上取最小值

那么平面上凸壳问题可以转化为凸包问题

考虑到 $CDQ$ 计算贡献:将第 $i-1$ 层设为操作,第 $i$ 层设为询问

第一维排序 $i$
第二位归并维护 $d[i]$ ,用栈维护凸包即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();};
    return ans * flag;
}
#define mid ((l + r) >> 1)
const int N = 100010;
const LL INF = LONG_LONG_MAX / 3;
int n, pos[N], len;
struct Node {
    LL a, b;
    LL d; 
    LL B, f;
    int g;
}p[N];
vector <int> e[N];
int q[N], qq[N];
int sta[N], top;
double slope(int a, int b) {
    return (1.0 * (p[b].B - p[a].B)) / (1.0 * (p[a].d - p[b].d));
}
void insert(int x) {
    while(top >= 2 && slope(x, sta[top]) >= slope(sta[top - 1], sta[top]))
        sta[top --] = 0;
    sta[++ top] = x; 
}
LL cal(int x) {
    return 1ll * x * (x - 1) / 2;
}
void query(int x) {
    if(!top) return;
    int l = 1, r = top;
    while(l <= r) {
        if(!sta[mid])
            p[x].f = min(p[x].f, p[x].a + p[x].b + cal(x));
        else
            p[x].f = min(p[x].f, (p[sta[mid]].d * x + p[sta[mid]].B) + p[x].a + p[x].b + cal(x));
        if(mid - 1 && slope(sta[mid], sta[mid - 1]) < x)
            r = mid - 1;
        else
            l = mid + 1;
    }
    if(p[x].d < 0)
        p[x].f = INF;
    p[x].B = p[x].f - p[x].d * (x + 1) - 1ll * cal(x + 1);
}
void clearStack() {
    while(top) sta[top --] = 0;
}
void cdq(int l, int r, int que) {
    if(l == r) return;
    cdq(l, mid, que); cdq(mid + 1, r, que);
    int q0 = l, q1 = mid + 1, head = l;
    while(q0 <= mid || q1 <= r) {
        if(q1 > r || (p[q[q0]].d <= p[q[q1]].d && q0 <= mid)) {
            if(p[q[q0]].g != que)
                insert(q[q0]);
            qq[head ++] = q[q0];
            ++ q0;
        }
        else {
            if(p[q[q1]].g == que)
                query(q[q1]);
            qq[head ++] = q[q1];
            ++ q1;
        }
    }
    clearStack();
    for(int i = l; i <= r; ++ i)
        q[i] = qq[i];
}
int main() {
    n = read();
    for(int i = 1; i <= n; ++ i)
        p[i].a = read();
    for(int i = 1; i <= n; ++ i)
        p[i].b = read();
    for(int i = 1; i <= n; ++ i)
        p[i].d = p[i].a - i;
    for(int i = 1; i <= n; ++ i)
        p[i].f = INF;
    pos[0] = p[0].d = - n; len = 0;
    e[0].push_back(0);
    for(int i = 1; i <= n; ++ i) {
        if(p[i].d < 0) continue;
        p[i].g = upper_bound(pos, pos + len + 1, p[i].d) - pos;
        pos[p[i].g] = p[i].d;
        len = max(len, p[i].g);
        e[p[i].g].push_back(i);
    }
    for(int i = 1; i <= len; ++ i) {
        int siz = 0;
        for(auto it : e[i - 1])
            q[++ siz] = it;
        for(auto it : e[i])
            q[++ siz] = it;
        sort(q + 1, q + siz + 1);
        cdq(1, siz, i);
    }
    printf("%d ", len);
    LL ans = INF;
    for(auto it : e[len])
        ans = min(ans , p[it].f + p[it].a * (n - it) + cal(n - it + 1));
    printf("%lld", ans);
    return 0;
}
Last modification:March 9th, 2019 at 04:02 pm

Leave a Comment