【BZOJ 3675】[Apio2014]序列分割

【链接】链接

【题意】

在这里输入题意

【题解】

模拟一下样例。
会发现。切的顺序不影响最后的答案。
只要切点确定了。
答案就确定了。
则设f[i][j]表示前i段,第i段保留到j的最大值。
$f[i][j] = max(f[i-1][x] + (s[j]-s[x])*(s[n]-s[j]))$
$s[i] = a[1] + a[2] +...+a[i]$
然后还是考虑x s[n]-s[j]$
而s[n]-s[j]是单调递减的;
这就能加一个斜率优化了。
注意这里是>s[n]-s[j]才y更优。
则队列的出入队和经典的斜率优化条件相反。
最后输出f[k+1][n]就好;
要用滚动数组。不然会MLE.

【错的次数】

在这里输入错的次数

【反思】

在这里输入反思

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e5,K = 200;

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

ll a[N+10],f[2][N+10],s[N+10];

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

{

    double fenzi = f[(i-1)&1][y] - f[(i-1)&1][x];

    double fenmu = s[y] - s[x];

    if (s[y]==s[x]) return 2e9;

    return fenzi/fenmu;

}

int main()

{

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

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

    for (int i = 1;i <= n;i++) scanf("%lld",&a[i]);

    for (int i = 1;i <= n;i++) s[i] = s[i-1] + a[i];

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

    {

        memset(f[i&1],0,sizeof f[i&1]);

        h = t = 1;

        dl[1] = 0;

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

            {

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

                int x = dl[h];

                f[i&1][j] = max(f[i&1][j],f[(i-1)&1][x] + (s[j]-s[x])*(s[n]-s[j]));

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

                dl[++t] = j;

            }

    }

    printf("%lld\n",f[(k+1)&1][n]);

    return 0;

}

巴特西

【BZOJ 3675】[Apio2014]序列分割

最新文章

热门文章