【BZOJ-4518】征途 DP + 斜率优化

4518: [Sdoi2016]征途

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

Solution

DP + 斜率优化

首先对所求的东西进行一下化简:

即最后的结果为$m*\sum_{i=1}^{m}x_{i}^{2}-\sum_{i=1}^{m}x_{i}$其中$x_{i}$表示第$i$天走的路段总和

很显然有$\sum_{i=1}^{m}x_{i}$为定值,那么只需要最小化$\sum_{i=1}^{m}x_{i}^{2}$

那么考虑$f[i][j]$表示$i$天共走了$j$段路的最优

首先可以有某天停滞不前,那么很容易发现,若要最优,则不可能停滞不前

可以得到转移$dp[i][j]=min(dp[i][j],dp[i-1][j-k]+(sum[j]-sum[j-k])^{2}),k=1-j$

那么固定下$i$后,很显然对于$j$是满足斜率优化的

那么化简就可以得到$\frac{dp[i-1][k_{1}]+sum[k_{1}]^{2}-dp[i-1][k_{2}]-sum[k_{2}]^{2}}{sum[k_{1}]-sum[k_{2}]}<2*sum[j]$

那么斜率优化即可,自己还打了个滚动数组,不过貌似毫无意义

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 3010
int n,m; int dis[maxn],que[maxn],l,r;
long long dp[][maxn],sum[maxn];
long long pf(long long x) {return x*x;}
inline double slope(int t,int i,int j)
{
return (double)(dp[t][i]+pf(sum[i])-dp[t][j]-pf(sum[j]))/(double)(sum[i]-sum[j]);
}
int main()
{
n=read(),m=read();
for (int i=; i<=n; i++) dis[i]=read(),sum[i]=sum[i-]+dis[i];
memset(dp,,sizeof(dp)); dp[][]=;
for (int t=,i=; i<=m; i++,t^=,l=r=)
for (int tmp,j=; j<=n; j++)
{
while (l<r && slope(t^,que[l],que[l+])<(sum[j]<<)) l++;
tmp=que[l];
dp[t][j]=pf(sum[j]-sum[tmp])+dp[t^][tmp];
while (l<r && slope(t^,que[r],que[r-])>slope(t^,que[r],j)) r--;
que[++r]=j;
}
printf("%lld\n",m*dp[m&][n]-pf(sum[n]));
return ;
}

在BZOJ上好像排名不高啊....

上一篇:Spring中整合Titles


下一篇:Dell R710、720等系列类服务器 U盘安装centos6.5 操作系统