Luogu 3648 [APIO 2014] 序列分割

• • • • • 傳送門
        • 思路
        • 正解
        • 參考代碼

傳送門

思路

  唉，我太弱了，什麼都不會，題又做不來，而且又讀錯題了。題目要求是切 k k 刀，我搞成了分成 kk 塊……幹脆

k++

算了。

  這道題顯然可以 DP，但是我一開始的狀态是這樣的：

fi,j=max{fs,j−2+g(s+1,i)} f i , j = max { f s , j − 2 + g ( s + 1 , i ) }

其中 g(l,r) g ( l , r ) 表示把 l l 到 rr 分成兩段的最大價值，這個可以在均攤 O(1) O ( 1 ) 的時間複雜度内計算出。

  然後我打開了一篇萬惡的讨論，看到了“斜率優化”四個字，然後我就嘗試在這個的基礎上變形，但是發現 g g 的計算方法除了均攤 O(1)O(1)（斜率優化時還不能用）就隻有最壞 O(logn) O ( log ⁡ n ) 的求法了。沒辦法，又涼了……

正解

  首先要發現這個狀态（ ai a i 表示 1∼i 1 ∼ i 的和，即字首和）：

fi,j=max{fs,j−1+as×(ai−as)} f i , j = max { f s , j − 1 + a s × ( a i − a s ) }

  他們怎麼這麼有本事，雖然很顯然切的順序不影響結果，但是他們就想到了 先切後面這一招。

  然後很顯然這個可以用斜率優化來做。雖然我學的斜率優化是假的，但是這并不重要，讓我們來試着用我的方法推一下。

  我們省略 max max 函數，展開裡面的式子得：

fi,j=fs,j−1+as×ai−as×as f i , j = f s , j − 1 + a s × a i − a s × a s

其中 s s 表示決策。

  若決策 s​s​ 比決策 t​ t ​ 更優（ s>t​ s > t ​ ），則有：

fs,j−1+as×ai−as×as>ft,j−1+at×ai−at×at f s , j − 1 + a s × a i − a s × a s > f t , j − 1 + a t × a i − a t × a t

  将包含 i i 的移向一邊，不包含 ii 的移向另一邊，則有：

(fs−ft)−(a2s−a2t)>ai(at−as) ( f s − f t ) − ( a s 2 − a t 2 ) > a i ( a t − a s )

  我們不妨設 at−as≠0 a t − a s ≠ 0 ，那麼顯然 at−as<0 a t − a s < 0 。則有：

(fs−ft)−(a2s−a2t)as−at>−ai ( f s − f t ) − ( a s 2 − a t 2 ) a s − a t > − a i

  顯然不等式右邊非嚴格單調遞減。設 h(s,t) h ( s , t ) 等于左式（ s>t s > t ），若 h(s,t)>−ai h ( s , t ) > − a i ，那麼 t t 永遠不再會是最優決策點。我們再設 s>t>ls>t>l，若 h(s,t)>h(t,l) h ( s , t ) > h ( t , l ) ，那麼 t t 永遠不會是最優決策點：若 h(s,t)>−aih(s,t)>−ai，則 t t 不是最優；若 h(s,t)≤−aih(s,t)≤−ai，則 h(t,l)<−ai h ( t , l ) < − a i ， t t 依然不是最優。

  現在唯一需要考慮的是 aj=aiaj=ai 的問題，這裡有一個一般人我都不告訴的技巧：将 as−at a s − a t 視為無限逼近 0 0 ，則斜率為正無窮，設成一個極大的數即可。

  輸出方案那還不簡單，儲存從哪裡轉移過來的即可。

  唉，我太弱了，就這麼個簡單的斜率優化我調了三節課，而且還沒有秒切，感覺自己學的斜率優化果然是假的。分母為 00 的情況也不是第一次見了，但是就是見一次忘一次，唉，太弱啦！

參考代碼

  注意一定要讓

k++

，把 k k <script type="math/tex" id="MathJax-Element-47">k</script> 了解成段數而不是分割點數目，這樣的轉移才是對的。否則一開始的狀态（

dq.push()

）是錯的。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
#define loop register int
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = ; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a *  - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[]; int length = ;
    if (x < ) putchar('-'); else x = -x;
    do buffer[length++] = -(x % ) + '0'; while (x /= );
    do putchar(buffer[--length]); while (length);
}

const int maxn = int() + ;
int n, k;
int a[maxn];
LL f[][maxn];
struct Deque
{
    int c[maxn];
    int head, tail;
    void clear() { head = tail = ; }
    int size() { return tail - head; }
    void push(int x) { c[tail++] = x; }
    void pop_front() { head++; }
    void pop_back() { tail--; }
    int front() { return c[head]; }
    int front2() { return c[head + ]; }
    int back() { return c[tail - ]; }
    int back2() { return c[tail - ]; }
} dq;

inline LL calcY(int i, int s) { return f[i][s] - (LL)a[s] * a[s]; }
inline LL deltaY(int i, int s, int t) { return calcY(i, s) - calcY(i, t); }
inline double slope(int i, int s, int t) { if (a[s] == a[t]) return ; return (double)deltaY(i, s, t) / (a[s] - a[t]); }
inline LL calc(int i, int j, int s)
{
    return f[i][s] + (LL)a[s] * (a[j] - a[s]);
}

int pre[][maxn];
void run()
{
    n = readIn();
    k = readIn();
    for (loop i = ; i <= n; i++)
        a[i] = readIn();
    for (loop i = ; i <= n; i++)
        a[i] += a[i - ];

    k++;
    for (loop i = ; i <= k; i++) // note
    {
        dq.clear();
        dq.push(i - ); // note
        for (loop j = i; j <= n; j++)
        {
            while (dq.size() >  && slope(i - , dq.front2(), dq.front()) > -a[j])
                dq.pop_front();
            f[i][j] = calc(i - , j, dq.front());
            pre[i][j] = dq.front();

            while (dq.size() >  && slope(i - , j, dq.back()) > slope(i - , dq.back(), dq.back2()))
                dq.pop_back();
            dq.push(j);
        }
    }
    printOut(f[k][n]);
    putchar('\n');
    std::vector<int> ans;
    int cnt = n;
    int t = k;
    for (int i = k; i; cnt = pre[i][cnt], i--)
        ans.push_back(pre[i][cnt]);
    for (int i = ans.size() - ; ~i; i--)
    {
        printOut(ans[i]);
        putchar(' ');
    }
}

int main()
{
    run();
    return ;
}