[BZOJ 3675][APIO 2014]序列分割(斜率優化DP)

題目連結

http://www.lydsy.com/JudgeOnline/problem.php?id=3675

思路

這題不是很難，但是坑了我一個下午+半個晚上才做出來，郁悶

首先設 f[i][k]=長度為i的序列，劃分了k次 得到的分數, sum[i]=∑it=1At ,即序列 A 的字首和

很容易推出DP方程：

f[i][k]=max{f[j][k−1]+sum[j](sum[i]−sum[j])}

f[i][k]=max{f[j][k−1]+sum[i]sum[j]−sum[j]2)}

這個DP複雜度是 O(n2k) 的，然後因為APIO很惡心地卡記憶體(128MB)，需要拿滾存減少記憶體占用，粗略估計如果常數優化得不錯的話，在實際比賽中能拿到50分左右(貌似apio的cu就到手了2333)。

然後看看能不能優化一下，發現這個DP其實很像一個斜率優化DP，可以通過優化來降低一維複雜度，變成大約是 O(nk) 的DP，恩可以拿到滿分

假設在DP到 f[i][t+1] 時，有兩個狀态 f[j][t] 和 f[k][t] 可供參考，假設 k<j ,且 j比k 優

f[j][t]+sum[i]sum[j]−sum[j]2>f[k][t]+sum[i]sum[k]−sum[k]2

f[j][t]−sum[j]2−f[k][t]+sum[k]2>sum[i]sum[k]−sum[i]sum[j]

sum[j]2−f[j][t]−sum[k]2+f[k][t]>sum[i](sum[k]−sum[j])

sum[j]2−f[j][t]−sum[k]2+f[k][t]sum[j]−sum[k]>sum[i]

再設 y[i][t]=sum[i]2−f[i][t]

y[j][t]−y[k][t]sum[j]−sum[k]>sum[i]

這玩意長得挺像斜率的。。。上面的不等式左邊當然是越大越好，是以最終我們需要維護一個上凸殼，每次決策時首先将那些隊首肯定不能充當最優解，而且以後也不能的元素都彈出隊列，然後用目前的隊首去更新 f ，然後将這個新的f放入隊尾，入隊前要維護這個隊列的單調性(上凸殼)

咦。。。好像原題中是要求輸出一個最大方案的(看來BZOJ的管理者太懶不願意造第二問資料2333)，這個就記錄下DP的前驅就好了

後記：

1、最好不要直接寫斜率的表達式，因為如果分母是0那麼就會出問題，最好把分母移到不等式的另一邊去

2、每次決策的2次出隊過程必須時刻保證隊列中至少有2個元素。

代碼

第一次做的，沒帶讀入優化，整整10s

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 100010
#define EPS 1e-6
#define INF 1000000000

using namespace std;

typedef long long int LL;

int n,m,h,t,q[MAXN];
LL f[MAXN][],sum[MAXN],y[MAXN][]; //f[i][j]=長度為i的序列，一共劃分了j次得到的最大分數
int now=; //now=目前用的下标

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
    {
        scanf("%lld",&sum[i]);
        sum[i]+=sum[i-];
    }
    for(int i=;i<=n;i++)
        y[i][]=sum[i]*sum[i];
    for(int j=;j<=m;j++) //劃分j次
    {
        now=-now;
        h=,t=;
        q[h]=;
        for(int i=;i<=n;i++) //長度為i的序列劃分j次
        {
            while(h<t&&sum[i]*(sum[q[h+1]]-sum[q[h]])>=(y[q[h+1]][-now]-y[q[h]][-now])) h++;
            f[i][now]=f[q[h]][-now]+sum[i]*sum[q[h]]-sum[q[h]]*sum[q[h]];
            y[i][now]=sum[i]*sum[i]-f[i][now];
            while(h<t&&(y[q[t]][-now]-y[q[t-1]][-now])*(sum[i]-sum[q[t]])>=(y[i][-now]-y[q[t]][-now])*(sum[q[t]]-sum[q[t-1]])) t--;
            q[++t]=i;
        }
    }
    printf("%lld\n",f[n][now]);
    return ;
}
           

第二次加入了讀入優化，略微快了幾百毫秒

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 100010
#define EPS 1e-6
#define INF 1000000000

using namespace std;

typedef long long int LL;

int n,m,h,t,q[MAXN];
LL f[MAXN][],sum[MAXN],y[MAXN][]; //f[i][j]=長度為i的序列，一共劃分了j次得到的最大分數,y[i][t]=sum[i]*sum[i]-f[i][t]
int now=; //now=目前用的下标

inline LL read()
{
    LL ans=;
    char ch=getchar();
    while(ch==' '||ch=='\n') ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans;
}

int main()
{
    n=(int)read(),m=(int)read();
    for(int i=;i<=n;i++)
    {
        sum[i]=read();
        sum[i]+=sum[i-];
    }
    for(int i=;i<=n;i++)
        y[i][]=sum[i]*sum[i];
    for(int j=;j<=m;j++) //劃分j次
    {
        now=-now;
        h=,t=;
        q[h]=;
        for(int i=;i<=n;i++) //長度為i的序列劃分j次
        {
            while(h<t&&sum[i]*(sum[q[h+1]]-sum[q[h]])>=(y[q[h+1]][-now]-y[q[h]][-now])) h++;
            f[i][now]=f[q[h]][-now]+sum[i]*sum[q[h]]-sum[q[h]]*sum[q[h]];
            y[i][now]=sum[i]*sum[i]-f[i][now];
            while(h<t&&(y[q[t]][-now]-y[q[t-1]][-now])*(sum[i]-sum[q[t]])>=(y[i][-now]-y[q[t]][-now])*(sum[q[t]]-sum[q[t-1]])) t--;
            q[++t]=i;
        }
    }
    printf("%lld\n",f[n][now]);
    return ;
}