[SDOI2016 Round1] 征途[斜率优化]

2225. [SDOI2016 Round1] 征途

★★★☆   输入文件：menci_journey.in   输出文件：menci_journey.out   简单对比
时间限制：1 s   内存限制：256 MB

【题目描述】

Pine 开始了从 S 地到 T 地的征途。

从 S 地到 T 地的路可以划分成 n 段，相邻两段路的分界点设有休息站。
Pine 计划用 m 天到达 T 地。除第 m 天外，每一天晚上 Pine 都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine 希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助 Pine 求出最小方差是多少。

设方差是 v，可以证明，v×m2 是一个整数。为了避免精度误差，输出结果时输出 v×m2。

【输入格式】

第一行两个数 n、m。

第二行 n 个数，表示 n 段路的长度。

【输出格式】

一个数，最小方差乘以 m2 后的值。

【样例输入】

5 2

1 2 5 8 6

【样例输出】

36

【提示】

对于 30% 的数据，1≤n≤10。
对于 60% 的数据，1≤n≤100。
对于 100% 的数据，1≤n≤3000。
保证从 S 到 T 的总路程不超过 30000。

【来源】

SDOI2016 Round1 Day2

数据已由出题人修正

我们把f[i][j]作为用过了第i次一共取了j个数的最小值.

斜率优化：

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

#define pf(x) ((x)*(x))

#define FRE(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);

#ifdef WIN32

#define LL "%I64d"

#else

#define LL "%lld"

#endif

const int N=;

int n,m,a[N],q[N];

ll ans,sum[N],f[N][N];

inline double get(int i,int x,int y){

    return ((double)(f[i][x]-f[i][y]+pf(sum[x])-pf(sum[y])))/((double)(sum[x]-sum[y]));

}

int main(){

    FRE(menci_journey);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-]+a[i];

    memset(f,0x3f3f3f3f,sizeof f);

    f[][]=;

    for(int i=;i<=m;i++){

        int h=,t=;

        for(int j=;j<=n;j++){

            while(h<t&&get(i-,q[h+],q[h])<(double)(sum[j]<<)) h++;//获取当前最优k

            f[i][j]=f[i-][q[h]]+pf(sum[j]-sum[q[h]]);

            while(h<t&&get(i-,q[t],q[t-])>get(i-,j,q[t])) t--;//维护min(slope)

            q[++t]=j;

        }

    }

    ans=f[m][n]*m-pf(sum[n]);

    printf(LL,ans);

    return ;

}