洛谷3648 [APIO2014]序列分割（斜率优化+dp）

首先对于这个题目。

qwq

存在一个性质就是，最终的答案只跟你的分割的位置有关，而和顺序无关。

举一个小栗子

$a\ b\ c$

将这个东西分成两块。

如果我们先分割$ab$之间的话，$ans = a*(b+c) + b*c$

如果先分割$bc$之间的话，$ans=c*(a+b)+a*b$

答案是一样的。（也可以理解成如果位置，两数相乘的次数是一定的）

那么得到这个结论之后

也就不难得出$dp$柿子了

\[dp[i][p]=max(dp[j][p-1]+(sum[i] + sum[j])\times sum[j])
\]

设$f[x]=dp[x]-sum[x]*sum[x]$

经过推柿子$$\frac{f[j]-f[k]}{sum[j]-sum[k]} > -sum[i]$$

然后直接上斜率优化

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk make_pair

#define ll long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 1e5+1e2;

struct Point

{

    ll x,y;

    int num;

};

ll chacheng(Point x,Point y)

{

    return x.x*y.y-x.y*y.x;

}

bool count(Point i,Point j,Point k)

{

    Point x,y;

    x.x=k.x-i.x;

    x.y=k.y-i.y;

    y.x=k.x-j.x;

    y.y=k.y-j.y;

    if (chacheng(x,y)>=0) return true;

    return false;

}

struct Node{

    Point q[maxn];

    ll head=1,tail=0;

    void push(Point x)

    {

        while (tail>=head+1 && count(q[tail-1],q[tail],x)) tail--;

        q[++tail]=x;

    }

    void pop(int lim)

    {

        while (tail>=head+1 && (q[head+1].y-q[head].y > lim * (q[head+1].x-q[head].x))) head++;

    }

};

Node q[210];

ll sum[maxn];

int n,k;

ll dp[2][210];

int pos[100010][210];

int main()

{

  n=read();k=read();

  k++;

  for (int i=1;i<=n;i++) sum[i]=read();

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

  q[0].push((Point){0,0,0});

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

  {

    for (int j=1;j<=min(i,k);j++)

    {

    	q[j-1].pop((-1)*sum[i]);

    	Point now = q[j-1].q[q[j-1].head];

    	dp[i&1][j]=now.y+now.x*now.x+(sum[i]-now.x)*now.x;

    	pos[i][j]=now.num;

    	q[j].push((Point){sum[i],dp[i&1][j]-sum[i]*sum[i],i});

    }

  }

  cout<<dp[n&1][k]<<endl;

  for (int i=n,j=k;i && j>1;i=pos[i][j],j--)

     cout<<pos[i][j]<<" ";

  cout<<endl;

  return 0;

}

巴特西

洛谷3648 [APIO2014]序列分割（斜率优化+dp）

最新文章

热门文章