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

attack

发布于 2018-04-13 16:14:55

1.1K0

发布于 2018-04-13 16:14:55

文章被收录于专栏：数据结构与算法数据结构与算法

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

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-04-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度