专栏首页数据结构与算法BZOJ4518: [Sdoi2016]征途(dp+斜率优化)

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • loj#2509. 「AHOI / HNOI2018」排列(思维题 set)

    首先不难看出如果我们从\(a_i\)向\(i\)连一条边,我们会得到以\(0\)为根的树(因为每个点一定都有一个入度,出现环说明无解),同时在进行排列的时候需要...

    attack
  • HDU1878 欧拉回路

    Problem Description 欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路? Inp...

    attack
  • P1967 货车运输 未完成

    1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<c...

    attack
  • 06--图解数据结构之并查集

    张风捷特烈
  • 复习C艹(更新中)

    之前在win7中运行c/c++下个vc就可以编译运行了,现在换了Mac,上网一看需要下个xcode,哎哟,好大啊,当时又没网,捉急,咦,mac的终端可以编译cp...

    仇诺伊
  • 短视频APP制作,设置高斯模糊

    yunbaokeji柯基
  • loj#2509. 「AHOI / HNOI2018」排列(思维题 set)

    首先不难看出如果我们从\(a_i\)向\(i\)连一条边,我们会得到以\(0\)为根的树(因为每个点一定都有一个入度,出现环说明无解),同时在进行排列的时候需要...

    attack
  • HDU1878 欧拉回路

    Problem Description 欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路? Inp...

    attack
  • 【每日算法Day 94】经典面试题:机器人的运动范围

    地上有一个 m 行 n 列的方格,从坐标 [0, 0] 到坐标 [m-1, n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、...

    godweiyang
  • light oj 1255 - Substring Frequency (KMP)

    裸裸的KMP,参考刘汝佳《算法竞赛入门经典训练指南》 P212 或数据结构。

    xindoo

扫码关注云+社区

领取腾讯云代金券