Chlience

【题解】BZOJ 4518 [SDOI 2016]征途
Problem传送门 >ω<题目大意:给定长度为 $n$ 的序列 $a_i$ ,将其分为 $m$ 段,最小化 $m...
扫描右侧二维码阅读全文
13
2018/10

【题解】BZOJ 4518 [SDOI 2016]征途

Problem

传送门 >ω<

题目大意:
给定长度为 $n$ 的序列 $a_i$ ,将其分为 $m$ 段,最小化 $m^2 *$ 方差

Solution

假设每一段的和为 $b[i] , S = \sum_{i = 1}^n a_i$

题目要求最小化 $m\sum_{i = 1}^m(b_i-\frac{S}{m})^2$

先变形

$$m\sum_{i = 1}^m(b_i-\frac{S}{m})^2$$
$$m(\sum_{i = 1}^m b_i^2 + \sum_{i=1}^m\frac{S^2}{m^2} - 2\sum_{i = 1}^{m}b_i\frac{S}{m})$$

发现 $\sum \frac{S^2}{m^2}$ 和 $\sum b_i\frac{S}{m^2}$ 其实是相同的

所以化简为

$$m[(\sum_{i = 1}^m b_i^2) - (\sum_{i = 1}^{m}\frac{S^2}{m^2})]$$

因为 $m , S$ 均为常数,所以对答案无影响,题目要求变为最小化

$$\sum_{i = 1}^{m}b_i^2$$

转移方程 $f[i] = min(f[j] + (sum[i] - sum[j])^2)$

发现这个东西是可以斜率优化的

$$\frac{(f[k] + sum[k]^2) - (f[j] + sum[j]^2)}{sum[k] - sum[j]} < 2sum[i],k>j$$

因为 $sum[i]$ 单调,所以显然是可以直接斜率优化的(不需要二分状态)
然后使用滚动数组枚举分割次数

这样就解决了这个问题,时间复杂度 $O(nm)$

代码

#include <bits/stdc++.h>
using namespace std;
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;
}

const int N = 3010;
int a[N] , sum[N];
int que[N] , l , r;
int f[N] , g[N];

double slope(int x , int y) {
    return (double)(g[y] - g[x] + sum[y] * sum[y] - sum[x] * sum[x]) / (double) (sum[y] - sum[x]);
}

int main() {
    int n = read() , m = read();
    for(int i = 1 ; i <= n ; ++ i) {
        a[i] = read();
        sum[i] = sum[i - 1] + a[i];
    }
    memset(g , 127 / 3 , sizeof(g));
    g[0] = 0;
    for(int i = 1 ; i <= m ; ++ i) {
        memset(que , 0 , sizeof(que)); l = 1 , r = 0;
        que[++ r] = 0;
        for(int j = 1 ; j <= n ; ++ j) {
            while(l < r && slope(que[l + 1] , que[l]) < 2 * sum[j]) ++ l;
            f[j] = g[que[l]] + (sum[j] - sum[que[l]]) * (sum[j] - sum[que[l]]);
            while(l < r && slope(que[r - 1] , que[r]) > slope(que[r] , j)) -- r;
            que[++ r] = j;
        }
        swap(f , g);
    }
    printf("%lld\n" , 1ll * g[n] * m - 1ll * sum[n] * sum[n]);
    return 0;
}

以为这样就结束了么,不可能的~

Solution

其实这个东西还可以进一步优化

考虑一下分块个数和最终答案的关系

显然是这样一个单调递减函数,需要求得在 $m$ 处得函数值

如果二分一个正比例函数,加入原函数中,那么这个函数会变成一个类似于 对勾函数 的形态

经过 DP 可以很简单的在 $O(n)$ 时间内找到这一导数为 0 的区域
本题中继续使用前文所说的斜率优化 DP ,并且不需要考虑限制

那么当我们二分正比例函数值时,一定能找到某个值使得 $m \in$ 导数为 0 的区域

这个时候再减正比例函数所增加的值,即为最优解

注意!
可能当你二分正比例函数时,只能取到 $m - x$ 或者 $m + x$ ($x$ 为非零常数)
所以在二分时动态记录和 $m$ 最接近的点答案,其答案与 $m$ 点答案等价(否则就能取到 $m$)

时间复杂度 $O(n\log v)$ $v$ 为二分值域

这样就过了这道 $n \leq 3000$ 的题~

代码

#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;
}

const int N = 3010;
LL a[N] , sum[N];
LL f[N] , g[N] , num[N];

int n , m;
int que[N];

double slope(int x , int y) {
    return (double)(g[y] - g[x] + sum[y] * sum[y] - sum[x] * sum[x]) / (double) (sum[y] - sum[x]);
}

int check(LL s) {
    memset(g , 127 / 3 , sizeof(g));
    memset(num , 0 , sizeof(num));
    memset(que , 0 , sizeof(que));
    int l = 1 , r = 0;
    g[0] = 0; que[++ r] = 0;
    for(int j = 1 ; j <= n ; ++ j) {
        while(l < r && slope(que[l + 1] , que[l]) < 2 * sum[j]) ++ l;

        g[j] = g[que[l]] + (sum[j] - sum[que[l]]) * (sum[j] - sum[que[l]]) + s;
        num[j] = num[que[l]] + 1;
        
        while(l < r && slope(que[r - 1] , que[r]) > slope(que[r] , j)) -- r;

        que[++ r] = j;
    }
    return num[n];
}

int main() {
    n = read() , m = read();
    for(int i = 1 ; i <= n ; ++ i) {
        a[i] = read();
        sum[i] = sum[i - 1] + a[i];
    }
    LL l = 0 , r = 1000000000000  , mid , ans = 0 , pos = 0 , now = 0;
    while(l <= r) {
        mid = (l + r) >> 1;
        int q = check(mid);
        if(q >= pos && q <= m) {ans = mid * m; pos = q; now = g[n];}
        //动态记录
        if(q == m) {break;}
        if(q > m) {l = mid + 1;}
        else {r = mid - 1;}
    }
    printf("%lld\n" , (now - ans) * m - sum[n] * sum[n]);
    return 0;
}
Last modification:October 13th, 2018 at 10:49 pm

Leave a Comment