[BZOJ4518][Sdoi2016]征途

可能斜率优化太弱.

4518: [Sdoi2016]征途

Time Limit: 10 Sec Memory Limit: 256 MB Submit: 2510 Solved: 1405 [Submit][Status][Discuss]

Description

Pine开始了从S地到T地的征途。 从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站。 Pine计划用m天到达T地。除第m天外,每一天晚上Pine都必须在休息站过夜。所以,一段路必须在同一天中走完。 Pine希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。 帮助Pine求出最小方差是多少。 设方差是v,可以证明,v×m^2是一个整数。为了避免精度误差,输出结果时输出v×m^2。

Input

第一行两个数 n、m。 第二行 n 个数,表示 n 段路的长度 Output

一个数,最小方差乘以 m^2 后的值

Sample Input

5 2

1 2 5 8 6

Sample Output

36 HINT

1≤n≤3000,保证从 S 到 T 的总路程不超过 30000

Source

鸣谢Menci上传

简要题解:

我们假设每一段的长度是 a_i,我们来看一下最后是什么东西。

得到ANS = m^2 * \frac {\sum_{i=1}^m (a_i-\bar{a}) }{m}

然后,我们一通转化:

ANS = m*\sum_{i=1}^m(a_i-\bar{a}) \\ 我们设 s = \sum_{i=1}^{m}ai \\ ANS = m*[ \sum_{i=1}^{m}a_i^2 + \sum_{i=1}^{m}(s/m)^2 - 2*\sum_{i=1}^{m}a_i * \frac{s}{m} ] \\ =m*\sum_{i=1}^{m}a_i^2 - 2*s^2 + s^2 \ = m*\sum_{i=1}^m a_i^2 - s^2

这样之后,我们就可以进行斜率优化转移dp了。斜率优化一种考虑方式就是尽可能将式子写成b + k*x = y的形式

例如本题,就是设f[k][x],表示已经分成k段,得到的SUMai^2和的最小值。

具体转化:

f[k][i] = min:f[k-1][j] + (sum[i]-sum[j])^2 (0\le j < i) \\ f[k][i] = f[k-1][j] + sum[i]^2 + sum[j]^2 - 2*sum[i]*sum[j] \\ f[k][i] + 2*sum[i]*sum[j] = f[k-1][j] + sum[j]^2 + sum[i]^2

在这里,我们把2*sum[i]看做斜率k,sum[i]^2是常数,把(sum[j],f[k-1][j]+sum[j] ^{2} )看做点的话,f[k][i] 为截距,由于随着i变大,x变大,斜率也变大,然后我们要截距最小,那么我们维护一个下凸包。对于这个过程,就是开一个队列,发现队首的斜率小于当前k就弹掉,并且随时弹掉队尾保证是下凸包。这样每次取的时候都是取到凸包切点处。

具体更多关于斜率优化的入门见大米饼大佬的博客

LJcode:


#include<bits/stdc++.h>
typedef double db;
#define int long long
const int maxn = 3005;
int n,m;

int st[maxn],hd,tl;
int f[maxn][maxn];
int CD[maxn],NOW;
db Y(int i) {
    return 1.0*(f[NOW][i] + CD[i]*CD[i]);
}
db X(int i) {
    return 1.0*(CD[i]);
}
db RATE(int x,int y) {
    return (Y(y)-Y(x))/(X(y)-X(x));
}

main() {
    //freopen("10.in","r",stdin);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%lld",&CD[i]); CD[i] += CD[i-1];
        f[1][i] = CD[i]*CD[i];
    }
    for(int k=2;k<=m;k++) {
        hd = 1; tl = 1; NOW = k-1; st[1] = k-1;
        for(int i=k;i<=n;i++) {
            while(hd<tl&&RATE(st[hd],st[hd+1])<2*CD[i]) hd++;
            f[k][i] = Y(st[hd]) + CD[i]*CD[i] - 2*CD[st[hd]]*CD[i];
            while( hd<tl && ( RATE(st[tl-1],st[tl]) > RATE(st[tl],i) ) ) tl--;
            st[++tl] = i;
        }
        for(int j=1;j<k;j++) f[k][j] = f[k-1][j];
       // std::cerr<<f[k][n]<<std::endl;
    }
    printf("%lld",m*f[m][n]-CD[n]*CD[n]);
} 
Last modification:July 3rd, 2019 at 03:39 pm

Leave a Comment