[BZOJ4518/Luogu4072][Sdoi2016]征途(动态规划,斜率优化)

发布于 2018-02-02  99 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4518/Luogu4072][Sdoi2016]征途(动态规划,斜率优化)

Description

Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外,每一天晚上Pine都必须在休息站过夜。所以,一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v,可以证明,v×m^2是一个整数。为了避免精度误差,输出结果时输出v×m^2。

Http

BZOJ
Luogu

Tag

动态规划,斜率优化

解决思路

先考虑答案是怎么算的,设\(Sum[i]\)表示前\(i\)段路的前缀和。
\[Ans=m^2*\frac{\sum_{i=1}^{m} (x_i- \bar x)^2}{m} \\ = m*(\sum_{i=1}^{m} x_{i}^{2}+m* {\bar x}^2-2*\sum_{i=1}^{m} x_i * \bar x) \\ =m*\sum_{i=1}^{m} x_{i}^2+Sum[n]^2-2*Sum[i]^2 \\ = m_{i=1}^{m} x_{i}^2-Sum[n]^2\]
那么这个式子就只与前面\(X_{i}^2\)这一项有关了,把这一项拿出来单独考虑。
设(F[i][j])表示前\(j\)个数分成\(i\)组使得上面那个\(X_{i}^2\)和最小,那么有下面的朴素转移方程
\[F[i][j]=min(F[i-1][k]+(Sum[j]-Sum[j])^2)\]
设\(j1 < j2\),且j2的答案更优,那么有
\[F[i-1][j1]+(Sum[i]-Sum[j1])^2 > F[i-1][j2]+(Sum[i]-Sum[j2])^2 \\ F[i-1][j1]+Sum[j1]^2-F[i-1][j2]-Sum[j2]^2 > 2*Sum[i]*(Sum[j1]-Sum[j2])\]
这样就可以斜率优化了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define sqr(x) (((ll)x)*(x))
#define Y(k,j1,j2) ((ll)F[k][j1]-(ll)F[k][j2]+(ll)sqr(Sum[j1])-(ll)sqr(Sum[j2]))
#define X(j1,j2) ((ll)Sum[j1]-(ll)Sum[j2])

const int maxN=3010;
const int inf=2147483647;

ll n,m;
ll Length[maxN],Sum[maxN],Queue[maxN];
ll F[maxN][maxN];

int main()
{
    scanf("%lld%lld",&n,&m);mem(F,63);F[0][0]=0;
    for (ll i=1;i<=n;i++) scanf("%lld",&Length[i]),Sum[i]=Sum[i-1]+Length[i];
    for (ll i=1;i<=m;i++)
    {
        ll l=0,r=0;
        for (ll j=1;j<=n;j++)
        {
            while ((l<r)&&(Y(i-1,Queue[l],Queue[l+1])>2*Sum[j]*X(Queue[l],Queue[l+1]))) l++;
            F[i][j]=F[i-1][Queue[l]]+sqr(Sum[j]-Sum[Queue[l]]);
            while ((l<r)&&(Y(i-1,Queue[r-1],Queue[r])*X(Queue[r],j)>Y(i-1,Queue[r],j)*X(Queue[r-1],Queue[r]))) r--;
            Queue[++r]=j;
        }
    }
    printf("%lld\n",(ll)m*F[m][n]-sqr(Sum[n]));
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4518/Luogu4072][Sdoi2016]征途(动态规划,斜率优化)


HNCJ OIer