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
     
      #include
      
       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=3005;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=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];    memset(f,0x3f3f3f3f,sizeof f);    f[0][0]=0;    for(int i=1;i<=m;i++){        int h=1,t=1;        for(int j=1;j<=n;j++){            while(h
       
        <(double)(sum[j]<<1)) h++;//获取当前最优k             f[i][j]=f[i-1][q[h]]+pf(sum[j]-sum[q[h]]);            while(h
        
         get(i-1,j,q[t])) t--;//维护min(slope)             q[++t]=j;        }    }    ans=f[m][n]*m-pf(sum[n]);    printf(LL,ans);    return 0;}