ปูพื้นฐาน

DP บนช่วง: จุดที่ต้องเลิกถามว่าทำอะไรที่ตำแหน่งนี้ แล้วหันไปถามทั้งช่วง

วิธีอ่านโจทย์ให้เจอสัญญาณว่า dp[i] ที่ใช้ได้มาตลอดกำลังจะพัง แล้วพาเปลี่ยน state จากจุดเป็นช่วง พร้อมเงื่อนไข "ตรงกลางต้องเกลี้ยง" ที่ทำให้ของคนละมุมมาเจอกันได้ พร้อมโจทย์ฝึก 3 ข้อที่ไล่ระดับกัน

อาการ · โจทย์ที่ทำให้ dp[i] พังทั้งใบ

ถ้าคุณเคยเขียน DP มาบ้าง คุณจะมีท่าประจำอยู่ท่าหนึ่ง คือตั้ง dp[i] ให้แปลว่า "ตัดสินใจกับ i ตัวแรกครบแล้ว ได้ค่าดีที่สุดเท่าไร" แล้วไล่จากซ้ายไปขวา ท่านี้ใช้ได้กับโจทย์จำนวนมหาศาล จนพอเจอโจทย์ที่มีคำว่า "ลบแล้วช่องปิด" ครั้งแรก คุณจะเขียนไปได้ครึ่งทางแล้วรู้สึกว่ามันไม่เข้ารูป แต่บอกไม่ถูกว่าไม่เข้าตรงไหน บทนี้จะพาไปดูว่ามันพังตรงไหน แล้วของที่ต้องใช้แทนหน้าตาเป็นยังไง

ลองกับแถวสั้น ๆ แถวหนึ่ง 1 2 3 1 3 ท่าแรกที่เกือบทุกคนลองคือกวาดจากซ้ายไปขวา เจอคู่ที่ซ้อนได้ก็ซ้อนทันที เริ่มที่ใบ 1 กับ 2 ต่างกัน 1 นิ้วพอดี ยกเลย เหลือ 3 1 3 ซึ่งไม่มีคู่ไหนต่างกันไม่เกิน 1 อีกแล้ว จบที่ เหลือ 3 ใบ

แต่คำตอบจริงคือ เหลือ 1 ใบ ทางที่ถูกคืออย่าเพิ่งแตะคู่แรก ยก 2 กับ 3 ตรงกลางออกก่อน โต๊ะจะเหลือ 1 1 3 ซึ่งทำให้จานใบที่ 1 กับใบที่ 4 ที่เดิมไม่เคยอยู่ติดกันเลย มาชนกันพอดี ยกออกอีกคู่ เหลือแค่ใบ 3 ใบเดียว

ทีนี้ลองถามตัวเองว่า dp[i] จะเก็บอะไร มันแปลว่า "จัดการจาน i ใบแรกเสร็จแล้ว" ซึ่งจะใช้ได้ก็ต่อเมื่ออดีตกับอนาคตติดต่อกันผ่านรอยต่อเดียว คือขอบขวาของสิ่งที่ทำไปแล้ว แต่ในโจทย์นี้ ของที่หายไปตรงกลางทำให้จานที่อยู่คนละฝั่งมาชนกันได้ พูดอีกอย่างคือ อดีตกับอนาคตยื่นมือข้ามหัวเราไปจับกันเอง ต่อให้คุณเติมมิติที่สองเข้าไปว่า "เหลือจานอะไรค้างอยู่บ้าง" คุณก็ต้องจำทั้งเซต ซึ่งบานเป็น 2ⁿ ทันที

ลองเอง · เก็บโต๊ะให้เหลือน้อยที่สุด

ก่อนจะไปดูวิธีคิด ลองเล่นเองสักพักครับ กดจานหนึ่งใบเพื่อเลือก แล้วกดใบที่อยู่ติดกันเพื่อยกทั้งคู่เข้าตู้ ยกได้เมื่อขนาดต่างกันไม่เกิน 1 เท่านั้น พอยกออกแล้วจานสองข้างจะเลื่อนมาชิดกันเอง ตัวเลข "ดีที่สุดที่ทำได้" คือคำตอบจริงของแถวนั้น ลองไล่ให้ถึงดู

ลองให้หนำใจก่อนนะครับ พอเริ่มรู้สึกว่า "ต้องมองไปข้างหน้าหลายตา" แล้วค่อยอ่านต่อ

ทางออก · เปลี่ยน state จากจุดเป็นช่วง

ปัญหาของ dp[i] คือมันบรรยายได้แค่ "ถึงไหนแล้ว" แต่โจทย์นี้ต้องการคำบรรยายที่บอกได้ว่า ตอนนี้เรากำลังพูดถึงของชิ้นไหนถึงชิ้นไหน เพราะการยกของออกมันเกิดขึ้นภายในช่วง แล้วผลของมันไม่รั่วออกนอกช่วงนั้นเลย ถ้าเรารู้ว่าช่วง [i..j] จัดการตัวเองจบแล้ว ข้างนอกไม่ต้องรู้เลยว่ามันจบยังไง รู้แค่ว่ามันเหลืออะไรทิ้งไว้ก็พอ

นั่นแหละคือที่มาของตารางสองมิติที่ดัชนีทั้งสองตัวเป็นปลายทั้งสองข้างของช่วง ไม่ใช่ตำแหน่งกับค่าอะไรสักอย่าง เรียกมันว่า keep[i][j] แปลว่า "ถ้ามองแค่จานในช่วง [i..j] ยกเข้าตู้ได้มากที่สุดกี่ใบ"

คำถามเดียวที่ต้องตอบให้ได้: จานซ้ายสุดจะไปคู่กับใคร

เวลาออกแบบสูตรของ DP บนช่วง อย่าไปคิดว่า "ยกคู่ไหนก่อนดี" เพราะลำดับการยกมีเป็นล้านแบบ ให้จับตัวใดตัวหนึ่งที่ไม่มีทางหนีเราได้ มาถามคำถามเดียว ตัวที่ง่ายที่สุดคือตัวซ้ายสุดของช่วง คือจานใบที่ i ชะตาของมันมีแค่สองแบบเท่านั้น

• ไม่มีใครเอามันไป มันค้างอยู่บนโต๊ะจนจบ งั้นทั้งช่วงก็เหลือปัญหาเดิมที่สั้นลงหนึ่งใบ คือ [i+1..j]
• มันถูกยกไปพร้อมกับจานใบที่ k สักใบที่อยู่ทางขวา ซึ่งจะเกิดขึ้นได้ต้องครบสองเงื่อนไข คือขนาดต่างกันไม่เกิน 1 และของที่ขวางอยู่ตรงกลางต้องถูกยกออกจนเกลี้ยง สองใบนี้ถึงจะได้มาชิดกัน

เงื่อนไขข้อหลังคือหัวใจของทั้งเรื่อง และเป็นจุดที่คนพลาดบ่อยที่สุด "เกลี้ยง" ต้องแปลว่าเกลี้ยงจริง ๆ ไม่ใช่ยกออกได้เยอะ ๆ แต่ยังเหลือสักใบ เพราะถ้าเหลือแม้ใบเดียวคาอยู่ตรงกลาง จานสองใบนั้นก็ไม่มีวันได้ชิดกัน

เขียนสองทางนั้นเป็นสมการได้แบบนี้ โดยที่ k ไล่ทุกตำแหน่งทางขวาที่เข้าเงื่อนไข

อ่านสูตรนี้ให้ออกต้องยึดหลักเดียว ทุกช่องในตารางตัดสินชะตาของจานซ้ายสุดของช่วงเท่านั้น คือใบที่ i ส่วนปลายขวา j ไม่ขยับเลยทั้งสองบรรทัด มันแค่บอกว่าตอนนี้เรามองโต๊ะแค่ถึงตรงไหน พอตัดสินใบที่ i เสร็จ ที่เหลือก็โยนต่อให้ช่องที่สั้นกว่าไปคิดแทน

• บรรทัดบน คือปล่อยใบที่ i ค้างไว้ ของที่เหลือคือช่วง [i+1..j] ซึ่งหน้าตาเหมือนโจทย์เดิมทุกอย่าง แค่สั้นลงหนึ่งช่อง ยอดที่ยกได้จึงเท่ากับ keep[i+1][j] ตรง ๆ ไม่มีของแถมเพิ่ม และท่านี้ใช้ได้เสมอ เพราะการไม่ทำอะไรไม่ต้องขออนุญาตใคร
• บรรทัดล่าง คือจับใบที่ i ไปคู่กับใบที่ k ทางขวา คู่นี้จะเกิดได้ก็ต่อเมื่อของที่ขวางอยู่ตรงกลางถูกยกออกจนเกลี้ยงไปก่อน และของตรงกลางที่หายไปนั้นนับเป็นผลงานของท่านี้ด้วย ยอดจึงเป็น k−i+1 คือทั้งช่วง [i..k] ส่วนที่ยังเหลือคือ [k+1..j] ซึ่งคิดต่อได้อิสระ เพราะเสาสองต้นที่เพิ่งปักลงไปตัดมันขาดจากก้อนซ้ายแล้ว

ตัว k ที่ห้อยอยู่ใต้ max แปลว่าเราลองทุกคู่ที่เป็นไปได้แล้วเก็บอันที่ดีที่สุดไว้ ไม่ใช่ตัวแปรที่ใครกำหนดมาให้ และเพราะทั้งสองบรรทัดวิ่งไปหาช่วงที่สั้นกว่าตัวเองเสมอ ตารางนี้จึงเติมได้โดยไม่มีวันวนกลับมาถามหาช่องที่ยังว่างอยู่

ทำไมต้องวนตามความยาว ไม่ใช่วนตามตำแหน่ง

สังเกตว่าช่องหนึ่ง ๆ ไปขอค่าจากช่อง [i+1..j], [i+1..k−1] และ [k+1..j] ซึ่งสั้นกว่าตัวมันเองเสมอ ถ้าเราวนตามตำแหน่ง i จากซ้ายไปขวาแบบที่ชินมือ เราจะไปขอค่าจากช่องที่ยังว่างอยู่ ทางที่ถูกจึงเป็นการไล่ตามความยาวช่วง ทำช่วงยาว 2 ให้ครบทุกตำแหน่งก่อน แล้วค่อยขยับไปยาว 3 ยาว 4 ไปเรื่อย ๆ ตอนถึงช่วงยาว L ทุกช่วงที่สั้นกว่า L เสร็จหมดแล้วแน่นอน

เดินตารางให้ดูจริง ทีละช่อง

เอาแถว 1 2 3 1 3 เมื่อกี้มาเติมตารางจริง แถวของตารางคือ i (ปลายซ้ายของช่วง) คอลัมน์คือ j (ปลายขวา) ช่องที่ i มากกว่า j ไม่มีความหมาย เลยเว้นว่างไว้ กดเดินทีละขั้นได้ ตารางจะค่อย ๆ เต็มจากเส้นทแยงมุมออกไปทางขวาบน พร้อมบอกว่าช่องนั้นเลือกทางไหนและทำไม

จุดที่น่าดูที่สุดคือตอนเติมช่อง keep[0][3] ซึ่งเป็นช่วง 1 2 3 1 ที่นั่นจานใบแรกเลือกจับคู่กับใบที่ 4 ได้ เพราะช่วงตรงกลาง [1..2] มีค่าในตารางเป็น 2 ซึ่งเท่ากับความยาวของมันพอดี แปลว่าเกลี้ยง นี่คือช่องที่เก็บ "ความรู้" ว่าตรงกลางหายหมดแล้ว ซึ่งเป็นความรู้ที่ dp[i] ไม่มีที่เก็บ

เขียนเป็นโค้ด

แปลสูตรลงโค้ดได้ตรง ๆ ลูปนอกสุดคือความยาว ลูปกลางคือจุดเริ่มของช่วง ลูปในสุดคือคู่ที่จะจับ ส่วน K กับ cleared เป็นแค่ตัวห่อไว้กันช่วงว่างเล็ดลอดออกนอกตาราง

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    // keep[i][j] = ยกออกได้มากที่สุดกี่ใบ ถ้ามองเฉพาะช่วง [i..j]
    vector<vector<int>> keep(n + 2, vector<int>(n + 2, 0));
    auto K = [&](int i, int j) { return i > j ? 0 : keep[i][j]; };
    // ช่วงที่ยกออกได้ "ครบทุกใบ" คือช่วงที่ค่าในตารางเท่ากับความยาวของมันพอดี
    auto cleared = [&](int i, int j) { return i > j || keep[i][j] == j - i + 1; };

    // วนตามความยาวช่วง ไม่ใช่ตามตำแหน่ง ช่วงสั้นต้องเสร็จก่อนช่วงยาวเสมอ
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            int best = K(i + 1, j);                    // ทิ้ง a[i] ไว้บนโต๊ะ
            for (int k = i + 1; k <= j; k++) {
                if (abs(a[i] - a[k]) > 1) continue;    // ขนาดไม่เข้าคู่
                if (!cleared(i + 1, k - 1)) continue;  // ของที่ขวางต้องหายเกลี้ยงก่อน
                best = max(best, (k - i + 1) + K(k + 1, j));
            }
            keep[i][j] = best;
        }
    }

    printf("%d\n", n - K(0, n - 1));   // เหลือบนโต๊ะกี่ใบ
    return 0;
}

นับงานดู ตารางมีช่องที่ใช้จริง n(n+1)/2 ช่อง แต่ละช่องไล่ k ได้ถึง n ครั้ง รวมเป็น O(n³) เวลา และ O(n²) หน่วยความจำ ที่ n = 300 คือราว 27,000,000 ครั้ง ซึ่งสบายมาก แต่ที่ n = 2,000 จะพุ่งเป็น 8,000,000,000 ครั้ง และตารางกินช่องถึง 2,001,000 ช่อง ตรงนี้แหละที่ทำให้ DP บนช่วงมีเพดานของมัน ถ้าโจทย์ให้ n ระดับหลักพันขึ้นไป แปลว่าเขาไม่ได้ตั้งใจให้ใช้ท่านี้ ต้องมองหามุมอื่นที่ยุบมิติทิ้งได้ ซึ่งเป็นเรื่องของบทถัดไป

// ตัวตรวจแบบซื่อ ๆ ลองยกทุกคู่ที่ยกได้ วนไปจนไม่มีอะไรให้ยก
// ช้ามาก ใช้ได้แค่ n เล็ก ๆ แต่มันคือสิ่งที่ทำให้เชื่อโค้ดข้างบนได้
#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> a) {
    int r = (int)a.size();
    for (size_t i = 0; i + 1 < a.size(); i++) {
        if (abs(a[i] - a[i + 1]) > 1) continue;
        vector<int> b = a;
        b.erase(b.begin() + i, b.begin() + i + 2);
        r = min(r, solve(b));
    }
    return r;
}

โจทย์ฝึก · ไล่จากง่ายไปยาก

สามข้อนี้เรียงมาให้ตอบคนละคำถาม ข้อแรกถามว่า "ต้องใช้ DP บนช่วงจริงหรือเปล่า" ข้อสองถามว่า "ท่านี้ใช้กับอย่างอื่นที่ไม่ใช่การลบได้ไหม" ข้อสามถามว่า "ถ้าเปลี่ยนสิ่งที่วัด จะพังตรงไหน" ลองคิดเองก่อนแล้วค่อยแตะเพื่อดูเฉลยครับ

ฝึกข้อ 1 ★☆☆☆☆ · แถวที่ลบคู่ฝาแฝด

// ฝึกข้อ 1: ลบคู่ที่ติดกันและเท่ากัน เหลือน้อยที่สุดกี่ตัว
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<int> st;
    st.reserve(n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        if (!st.empty() && st.back() == x) st.pop_back();   // เจอฝาแฝด หายไปทั้งคู่
        else st.push_back(x);
    }
    printf("%d\n", (int)st.size());
    return 0;
}

ฝึกข้อ 2 ★★☆☆☆ · เติมวงเล็บให้ครบ

// ฝึกข้อ 2 ท่าที่ 1: DP บนช่วง O(n^3)
// f[i][j] = ต้องเติมวงเล็บอย่างน้อยกี่ตัว ช่วง [i..j] ถึงจะถูกกติกา
#include <bits/stdc++.h>
using namespace std;

int main() {
    char buf[512];
    if (scanf("%s", buf) != 1) return 0;
    string s = buf;
    int n = (int)s.size();
    vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));

    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (len == 1) { f[i][j] = 1; continue; }   // ตัวเดียวโดด ๆ ต้องเติมคู่ให้เสมอ
            int best = INT_MAX;
            // หัวกับท้ายจับคู่กันได้พอดี ที่เหลือคือปัญหาย่อยตรงกลาง
            if (s[i] == '(' && s[j] == ')') best = min(best, i + 1 <= j - 1 ? f[i + 1][j - 1] : 0);
            // ไม่งั้นก็ผ่าเป็นสองท่อนที่ไม่ยุ่งกัน
            for (int k = i; k < j; k++) best = min(best, f[i][k] + f[k + 1][j]);
            f[i][j] = best;
        }
    }
    printf("%d\n", n == 0 ? 0 : f[0][n - 1]);
    return 0;
}

// ฝึกข้อ 2 ท่าที่ 2: ตัวนับตัวเดียว O(n)
// open = วงเล็บเปิดที่ยังไม่มีใครมาปิด, add = วงเล็บปิดที่หาเจ้าของไม่ได้
#include <bits/stdc++.h>
using namespace std;

int main() {
    char buf[512];
    if (scanf("%s", buf) != 1) return 0;
    int open = 0, add = 0;
    for (char *p = buf; *p; p++) {
        if (*p == '(') open++;
        else if (open > 0) open--;      // ไปปิดตัวที่ค้างอยู่
        else add++;                     // ไม่มีใครให้ปิด ต้องเติมตัวเปิดข้างหน้า
    }
    printf("%d\n", add + open);
    return 0;
}

ฝึกข้อ 3 ★★★☆☆ · เปลี่ยนสิ่งที่วัด

// ฝึกข้อ 3: กติกาเดิม แต่แต้มคือผลรวมขนาดจานที่ยกออก อยากได้แต้มมากที่สุด
// ต้องมีสองตาราง full บอกว่าช่วงนั้นยกออกได้เกลี้ยงไหม (ไม่เกี่ยวกับแต้ม)
// ส่วน val เก็บแต้มสูงสุด ถ้าเอาตารางแต้มมาตัดสินเรื่องเกลี้ยงจะผิด
// เพราะทางที่แต้มสูงสุดไม่จำเป็นต้องเป็นทางที่ยกออกได้เยอะสุด
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    vector<vector<char>> full(n + 2, vector<char>(n + 2, 0));
    vector<vector<long long>> val(n + 2, vector<long long>(n + 2, 0));
    auto isFull = [&](int i, int j) { return i > j ? true : (bool)full[i][j]; };
    auto V = [&](int i, int j) { return i > j ? 0LL : val[i][j]; };

    for (int len = 2; len <= n; len++)
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            for (int k = i + 1; k <= j; k++)
                if (abs(a[i] - a[k]) <= 1 && isFull(i + 1, k - 1) && isFull(k + 1, j)) {
                    full[i][j] = 1;
                    break;
                }
        }

    for (int len = 2; len <= n; len++)
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            long long best = V(i + 1, j);
            for (int k = i + 1; k <= j; k++) {
                if (abs(a[i] - a[k]) > 1) continue;
                if (!isFull(i + 1, k - 1)) continue;
                best = max(best, a[i] + a[k] + V(i + 1, k - 1) + V(k + 1, j));
            }
            val[i][j] = best;
        }

    printf("%lld\n", V(0, n - 1));
    return 0;
}

ยุบอีกชั้น · Knuth optimization

DP บนช่วงที่บทนี้สอนมีต้นทุน O(n³) คือช่อง n² ช่อง ช่องละไล่จุดตัด n จุด ซึ่งพอสำหรับ n ระดับห้าร้อยถึงพัน แต่มีโจทย์ที่ให้ n ถึงสองสามพัน แล้วทางนี้ก็ตกเวลาไปเฉย ๆ

สำหรับ DP บนช่วงรูปหนึ่งที่พบบ่อยมาก มีท่าที่ยุบ O(n³) ลงเป็น O(n²) โดยไม่เปลี่ยนสมการเลย เปลี่ยนแค่ขอบเขตของลูปในสุด ท่านั้นชื่อ Knuth optimization (ตามชื่อ Donald Knuth)

ตรงนี้เล่าแบบย่อพอให้ใช้งานได้ ถ้าอยากได้ที่มาว่าทำไมข้ออ้างข้างล่างถึงเป็นจริง ทำไมหน้าต่างที่แคบลงนิดเดียวถึงยุบได้ทั้งอันดับ และตัวอย่างค้านที่ทำให้มันตอบผิดแบบเงียบ ๆ อยู่ในบทเร่งดีพีบนช่วงแบบคะนูธ ซึ่งมีโจทย์ฝึกให้อีกสามข้อ

ข้ออ้างที่ทำให้ตัดงานได้

เก็บเพิ่มอีกตารางหนึ่งชื่อ opt[i][j] แปลว่าจุดตัดที่ดีที่สุดของช่วง [i..j] ข้ออ้างของ Knuth คือจุดตัดที่ดีที่สุดนั้นขยับไปทางขวาอย่างเป็นระเบียบ เมื่อช่วงยาวขึ้น เขียนเป็นอสมการได้ว่า

opt[i][j−1] ≤ opt[i][j] ≤ opt[i+1][j]

ความหมายเชิงรูปคือ ถ้าเรารู้จุดตัดที่ดีที่สุดของช่วงที่สั้นกว่าหนึ่งช่องทั้งสองแบบแล้ว จุดตัดที่ดีที่สุดของช่วงนี้ต้องอยู่ระหว่างสองค่านั้น ไม่มีทางหลุดออกไป เราจึงไล่จุดตัดแค่ในช่วงแคบนั้น แทนที่จะไล่ตั้งแต่ i ถึง j-1

ที่มันกลายเป็น O(n²) ไม่ใช่เพราะแต่ละช่องเร็วขึ้นเท่า ๆ กัน บางช่องยังไล่ยาวเหมือนเดิม แต่ผลรวมของความยาวที่ไล่ ทั้งแถวเดียวกัน มีเพดานที่ n เพราะขอบซ้ายกับขอบขวาของช่วงที่ไล่ ต่างก็ขยับไปทางขวาอย่างเดียว เป็นการนับต้นทุนแบบเฉลี่ยทบ เหมือนที่สองตัวชี้ในบทหน้าต่างเลื่อน ใช้

// Knuth optimization: รวมกองหินให้เหลือกองเดียว ค่าใช้จ่ายน้อยที่สุด
// dp[i][j] = ค่าน้อยสุดที่รวมช่วง i..j และ opt[i][j] = จุดตัดที่ดีที่สุดของช่วงนั้น
// ข้ออ้างที่ทำให้เร็วขึ้น: opt[i][j-1] <= opt[i][j] <= opt[i+1][j]
// จึงไล่จุดตัดแค่ช่วงแคบ ๆ แทนที่จะไล่ทั้งช่วง ทำให้ O(n^3) ยุบเป็น O(n^2)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<long long> a(n + 1, 0), pre(n + 1, 0);
    for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); pre[i] = pre[i - 1] + a[i]; }
    auto sum = [&](int i, int j) { return pre[j] - pre[i - 1]; };

    const long long INF = (long long)4e18;
    vector<vector<long long>> dp(n + 2, vector<long long>(n + 2, 0));
    vector<vector<int>> opt(n + 2, vector<int>(n + 2, 0));
    for (int i = 1; i <= n; i++) { dp[i][i] = 0; opt[i][i] = i; }

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INF;
            int lo = opt[i][j - 1];
            int hi = (i + 1 <= j) ? opt[i + 1][j] : j - 1;
            lo = max(lo, i);
            hi = min(hi, j - 1);
            for (int k = lo; k <= hi; k++) {
                long long cand = dp[i][k] + dp[k + 1][j] + sum(i, j);
                if (cand < dp[i][j]) { dp[i][j] = cand; opt[i][j] = k; }
            }
        }
    }
    printf("%lld\n", n == 0 ? 0 : dp[1][n]);
    return 0;
}

// ตัวตรวจอิสระของ Knuth: DP บนช่วงแบบไล่จุดตัดทุกจุด ไม่ใช้ข้ออ้างเรื่อง opt เลย
// นี่คือ O(n^3) ตรง ๆ ซึ่งเป็นสิ่งที่ Knuth พยายามหลบ จึงเป็นการตรวจที่อิสระจริง
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<long long> a(n + 1, 0), pre(n + 1, 0);
    for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); pre[i] = pre[i - 1] + a[i]; }
    auto sum = [&](int i, int j) { return pre[j] - pre[i - 1]; };
    const long long INF = (long long)4e18;
    vector<vector<long long>> dp(n + 2, vector<long long>(n + 2, 0));
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INF;
            for (int k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum(i, j));
        }
    printf("%lld\n", n == 0 ? 0 : dp[1][n]);
    return 0;
}

สรุปบรรทัดเดียว

พอโจทย์บอกว่าลบแล้วช่องปิด ให้เลิกถามว่า "ทำอะไรที่ตำแหน่งนี้" แล้วเปลี่ยนไปถามว่า "ช่วงนี้จัดการตัวเองจบแล้วเหลืออะไร" จับตัวซ้ายสุดของช่วงมาถามว่ามันจะไปคู่กับใคร เติมตารางไล่ตามความยาวช่วงเสมอ แล้วอย่าลืมว่าเงื่อนไข "ตรงกลางต้องเกลี้ยง" คือสิ่งเดียวที่ทำให้ของสองชิ้นคนละมุมมาเจอกันได้

DP บนช่วงไม่ได้ยากที่สูตร มันยากที่การยอมเลิกมองแถวเป็นเส้นตรงที่เดินจากซ้ายไปขวา แล้วหันมามองมันเป็นกล่องที่ซ้อนกันอยู่