BZOJ4518: [Sdoi2016]征途(dp+斜率优化)

2018-06-17 20:52:55来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 1875  Solved: 1045
[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上传

 
其实这题并不是很难,只怪自己太垃圾
首先我们把题目中给出的式子拆开
然后暴力推,发现最终答案只与$v_i^2$有关,$v_i$为拆出来的每个区间的长度
这样我们令$f[i][j]$表示前$i$个元素,选出了$j$段区间的最优方案
 $$f[i][j]=min(f[i][j],\sum_{k=1}^{i-1} f[k][j-1])$$
然后暴力推推推,
最终可以化简为$$f[i][l]+2sum[i]sum[j]=f[j][l-1]+sum[j]^2$$
$sum[i]$为$i$的前缀和。
这样的话就可以愉快的斜率优化啦
第二维可以用滚动数组滚动掉
 
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cmath>
#include<algorithm>
#define int long long 
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
using namespace std;
const int MAXN=1e5+10;
const int limit=100000;
int N,M;
int f[MAXN],g[MAXN];
int sum[MAXN];
int sqr(int x) {return x*x;}
int Query(int l,int r){return sum[r]-sum[l-1];}
int X(int x){return sum[x];}
int Y(int x){return g[x]+sqr(sum[x]);}
int slope(int x,int y){return (Y(y)-Y(x)) / (X(y)-X(x));}
int Q[MAXN];
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    //freopen("b.out","w",stdout);
    #endif
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) scanf("%d",&sum[i]),sum[i]+=sum[i-1];
    for(int i=1;i<=N;i++) g[i]=sqr(sum[i]);
    for(int k=1;k<=M-1;k++)
    {
        memset(f,0x3f,sizeof(f));
        int h=1,t=1;Q[1]=k-1;
        for(int i=k+1;i<=N;i++)
        {
            while(h<t&&slope(Q[h],Q[h+1])<2*sum[i]) h++;
            int j=Q[h];
            f[i]=min(f[i],g[j]+sqr(Query(j+1,i)));
            while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i)) t--;
            Q[++t]=i;
        }
        
        memcpy(g,f,sizeof(f));
    }
    printf("%lld",-sum[N]*sum[N]+f[N]*M);
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:BZOJ 3524: [POI2014]KUR-Couriers

下一篇:BZOJ2783: [JLOI2012]树(树上前缀和+set)