【BZOJ 4518】[Sdoi2016]征途

【链接】链接

【题意】

在这里输入题意

【题解】

DP+斜率优化;
$D(x) = E(x^2)-E(x)^2$
其中$E(x)^2$这一部分是确定的。
因为总长是确定的,分成的段数又是确定的。
所以我们只要维护$E(x^2)$这一部分最小就可以了。
而最后答案又要乘上m^2
把E(X^2)的表达式写出来;
会发现就是在维护
$m*(s1^2+s2^2+...+sm^2)$最小
具体的
设dp[i][j]表示前i天分配了前j段路的$m*(s1^2+s2^2+..)$的最小值
dis[i]为距离的前缀和
$dp[i][j] = min(dp[i-1][x]+m*{(dis[j]-dis[x])}^2)$
复杂度是$O(N^3)$的。
然后考虑x

【错的次数】

在这里输入错的次数

【反思】

在这里输入反思

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 3e3;

int n,m,d[N+10];

ll dp[N+10][N+10];

int dl[N+10],h,t;

ll sqr(ll x)

{

    return x*x;

}

double ju(int i,int x,int y)

{

    double fenzi = dp[i-1][y]+m*sqr(d[y]) - (dp[i-1][x] + m*sqr(d[x]));

    double fenmu = 2*m*(d[y]-d[x]);

    return fenzi/fenmu;

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    scanf("%d%d",&n,&m);

    for (int i = 1;i <= n;i++)

    {

        scanf("%d",&d[i]);

        d[i]+=d[i-1];

    }

    for (int i = 0;i <= N;i++)

        for (int j = 0;j <= N;j++)

            dp[i][j] = 1e17;

    dp[0][0] = 0;

    for (int i = 1;i <= m;i++)

    {

        h = 1,t = 1;

        for (int j = 1;j <= n;j++)

        {

            while (h < t && ju(i,dl[h],dl[h+1]) < d[j]) h++;

            dp[i][j] = min(dp[i][j],dp[i-1][dl[h]]+1LL*m*sqr(d[j]-d[dl[h]]));

            while (h < t && ju(i,dl[t-1],dl[t]) > ju(i,dl[t],j)) t--;

            t++;

            dl[t] = j;

        }

    }

    printf("%lld\n",dp[m][n]-sqr(d[n]));

    return 0;

}

巴特西

【BZOJ 4518】[Sdoi2016]征途

最新文章

热门文章