洛谷3648 [APIO2014]序列分割

Luogu

BZOJ

分析

容易发现分割的顺序对答案没有影响。

先写一个$O(n^2k)$的暴力DP。

设$f[i][j]$表示前$j$个数切$i$次的最大得分,$sum$是$a$的前缀和,那么有

$f[i][j]=\max\limits_{k=1}^{j-1}\big[f[i-1][k]+sum[k]\times(sum[j]-sum[k])\big]$

假设$k$比$l$优,那么有

$f[i-1][k]+sum[k]\times sum[j]-sum[k]^2>f[i-1][l]+sum[l]\times sum[j]-sum[l]^2$

$sum[k]\times sum[j]-sum[l]\times sum[j]>f[i-1][l]-f[i-1][k]-sum[l]^2+sum[k]^2$

$(sum[k]-sum[l])\times sum[j]>sum[k]^2-sum[l]^2-f[i-1][k]+f[i-1][l]$

$\large\frac{sum[k]^2-sum[l]^2-f[i-1][k]+f[i-1][l]}{sum[k]-sum[l]}<sum[j]$

这些东西都是单调的,然后就可以做到$O(nk)$了。

代码

Luogu

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define sqr(x) ((x)*(x))
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;
const int MAXK=200+10;

int n,k;
ll sum[MAXN];
ll f[MAXK][MAXN];
int pre[MAXK][MAXN];
int Q[MAXN],h=1,t=1;

inline void Print(int k,int n) {
    if (!k) return;
    Print(k-1,pre[k-1][n]);
    printf("%d ",n);
}

inline double slope(int i,int j,int p) {
    if (sum[i]==sum[j]) return -2e14;
    return 1.0*(sqr(sum[i])-sqr(sum[j])-f[p][i]+f[p][j])/(sum[i]-sum[j]);
}

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) sum[i]=sum[i-1]+read();
    for (re int p=1;p<=k;++p) {
        h=t=1;
        for (re int i=1;i<=n;++i) {
            while (h<t&&slope(Q[h],Q[h+1],p-1)<=sum[i]) ++h;
            f[p][i]=f[p-1][Q[h]]+sum[Q[h]]*(sum[i]-sum[Q[h]]);
            pre[p][i]=Q[h];
            while (h<t&&slope(Q[t-1],Q[t],p-1)>=slope(Q[t],i,p-1)) --t;
            Q[++t]=i;
        }
    }
    printf("%lld\n",f[k][n]);
    Print(k,pre[k][n]);
    putchar('\n');
    return 0;
}

BZOJ

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define sqr(x) ((x)*(x))
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;
const int MAXK=200+10;

int n,k;
ll sum[MAXN];
ll f[2][MAXN];
int pre[MAXK][MAXN];
int Q[MAXN],h=1,t=1;

inline void Print(int k,int n) {
    if (!k) return;
    Print(k-1,pre[k-1][n]);
    printf("%d ",n);
}

inline double slope(int i,int j,int p) {
    if (sum[i]==sum[j]) return -2e14;
    return 1.0*(sqr(sum[i])-sqr(sum[j])-f[p][i]+f[p][j])/(sum[i]-sum[j]);
}

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) sum[i]=sum[i-1]+read();
    for (re int p=1;p<=k;++p) {
        int now=p&1,lst=now^1; h=t=1;
        for (re int i=1;i<=n;++i) {
            while (h<t&&slope(Q[h],Q[h+1],lst)<=sum[i]) ++h;
            f[now][i]=f[lst][Q[h]]+sum[Q[h]]*(sum[i]-sum[Q[h]]);
            pre[p][i]=Q[h];
            while (h<t&&slope(Q[t-1],Q[t],lst)>=slope(Q[t],i,lst)) --t;
            Q[++t]=i;
        }
    }
    printf("%lld\n",f[k&1][n]);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 56 PM

发表评论