programming.in.th

หยิบหนังสือ: เมื่อสูตรตอบไม่ได้ ให้เปลี่ยนคำถาม อย่าเปลี่ยนสูตร

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

โจทย์ · หยิบหนังสือ

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

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

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

ชุดที่ 2 อ่านง่ายที่สุด มีเลข 5 อยู่แปดเล่ม แล้วมีเลข 100 นอนรออยู่ล่างสุด

ตรงไหนที่ทำให้ข้อนี้ไม่ง่าย

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

ลองเอง · กองหนังสือจำลอง

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

ลองเล่นให้หนำใจก่อนนะครับ พอมีคำตอบในใจแล้วค่อยเปิดเฉลย

เฉลย ตอนที่ 1 · ทำไมการรีบคว้าก้อนใหญ่ถึงแพ้

เฉลย ตอนที่ 2 · เปลี่ยนคำถามจาก "หยิบตรงไหน" เป็น "ใครได้บวก ใครได้ลบ"

เฉลย ตอนที่ 3 · กฎของเครื่องหมายที่ทำได้จริง

เฉลย ตอนที่ 4 · เหลือแค่ตารางเดียว

// cur[q] คือ dp[i][q] แถวที่กำลังยืนอยู่  ส่วน nxt[q] คือ dp[i+1][q] แถวถัดไป
// ยืนที่ช่องปลายทาง nxt[q] แล้วเก็บค่าที่ดีที่สุดจากสามทางที่ชี้เข้ามา
long long best = NEG;
if (q == 0 && cur[0] != NEG)         best = max(best, cur[0]);            // ไม่หยิบเล่มนี้เลย
if (q >= 1 && cur[q - 1] != NEG)     best = max(best, cur[q - 1] + a[i]); // ให้เป็นบวก
if (q + 2 <= n && cur[q + 2] != NEG) best = max(best, cur[q + 2] - a[i]); // ให้เป็นลบ
nxt[q] = best;

// ท่ากลับด้าน ยืนที่ช่องต้นทาง cur[p] แล้วส่งค่าออกไปสามช่อง
// ต้อง fill(nxt, NEG) ก่อนเข้าลูปนี้ เพราะช่องปลายทางถูกเขียนหลายครั้ง
long long v = cur[p];
if (v == NEG) continue;
if (p == 0)   nxt[0]     = max(nxt[0],     v);        // ไม่หยิบเล่มนี้เลย
nxt[p + 1]               = max(nxt[p + 1], v + a[i]); // ให้เป็นบวก
if (p >= 2)   nxt[p - 2] = max(nxt[p - 2], v - a[i]); // ให้เป็นลบ

โค้ด C++

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

#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]);

    // cur[p] = แต้มมากสุด เมื่อดูหนังสือไปแล้ว i เล่ม และยังมี "บวกค้าง" อยู่ p เล่ม
    // NEG = สถานะที่ไปไม่ถึง (ใช้ 0 ไม่ได้ เพราะ 0 เป็นแต้มที่ถูกต้องได้)
    const long long NEG = LLONG_MIN / 4;
    vector<long long> cur(n + 1, NEG), nxt(n + 1, NEG);
    cur[0] = 0;

    for (int i = 0; i < n; i++) {
        // ยืนที่ช่องปลายทาง nxt[q] แล้วถามว่ามันรับค่ามาจากช่องไหนของ cur ได้บ้าง
        for (int q = 0; q <= n; q++) {
            long long best = NEG;
            // เล่มนี้ไม่ถูกหยิบเลย มาได้จากช่องที่ไม่มีบวกค้างเท่านั้น
            if (q == 0 && cur[0] != NEG) best = max(best, cur[0]);
            // เล่มนี้เป็นบวก ก่อนหน้าจึงค้างน้อยกว่าหนึ่งเล่ม
            if (q >= 1 && cur[q - 1] != NEG) best = max(best, cur[q - 1] + a[i]);
            // เล่มนี้เป็นลบ กินบวกค้างไปสอง ก่อนหน้าจึงค้างมากกว่าสองเล่ม
            if (q + 2 <= n && cur[q + 2] != NEG) best = max(best, cur[q + 2] - a[i]);
            nxt[q] = best;   // เขียนทับทุกช่องของแถว จึงไม่ต้องล้างแถวก่อน
        }
        swap(cur, nxt);
    }

    printf("%lld\n", cur[0]);            // จบแบบไม่มีบวกค้าง = ทุกครั้งที่หยิบสมบูรณ์
    return 0;
}

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

long long best(vector<int> a) {
    long long r = 0;                     // 0 = เลือกที่จะหยุดหยิบตรงนี้
    for (size_t i = 0; i + 2 < a.size(); i++) {
        vector<int> b = a;
        long long gain = (long long)b[i] + b[i + 1] - b[i + 2];
        b.erase(b.begin() + i, b.begin() + i + 3);
        r = max(r, gain + best(b));
    }
    return r;
}

ทางที่คนคิดถึงก่อน · DP บนช่วง และเหตุผลของลิมิต 16 เมกะไบต์

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

คิดแบบช่วง: ให้ตารางจำว่าช่วงไหนถูกกวาดเรียบแล้ว

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

เหตุผลที่คนคิดถึงท่านี้ก่อนคือมันตอบเรื่อง "กองปิดช่องเอง" ได้ตรง ๆ ถ้าเรารู้ว่าช่วง [x+1..y−1] ถูกกวาดออกไปหมดแล้ว เราก็รู้ทันทีว่าเล่ม x กับเล่ม y จะมาอยู่ติดกัน โดยไม่ต้องสนใจว่าข้างในมันหยิบกันยังไง นิยามที่ได้คือ

เล่มซ้ายสุดของช่วงต้องไปจับคู่กับใคร

ทีนี้มาหาสมการ ในช่วง [i..j] ที่ต้องกวาดให้เกลี้ยง เล่ม i ซึ่งเป็นเล่มบนสุดต้องหลุดออกไปกับการหยิบสักครั้งหนึ่ง การหยิบครั้งนั้นประกอบด้วยเล่ม i เล่ม x และเล่ม y โดยที่ i < x < y เล่ม i กับ x เป็นบวก เล่ม y เป็นลบ

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

เขียนเป็นสมการได้ตรง ๆ แบบนี้

สมการนี้ยังแพงเกินไป และแก้ได้แค่ครึ่งเดียว

ลองนับงานดู สถานะมี n² ช่อง และการหาค่าของแต่ละช่องต้องไล่คู่ (x, y) ซึ่งมีอยู่ n² คู่ รวมเป็น O(n⁴) ซึ่งแตะไม่ได้เลยที่ n เท่ากับ 2,000

ท่าที่ช่วยได้คือแยกการเลือก x ออกจากการเลือก y เพราะสองตัวนี้ไม่ได้พันกัน สร้างตารางช่วยอีกใบชื่อ t[i][y] แปลว่า "ให้เล่ม i กับเล่ม x สักตัวเป็นบวก แล้วเคลียร์ของแทรกจนพร้อมจะไปเจอเล่ม y ได้แต้มสูงสุดเท่าไหร่"

พอมี t แล้ว ตัวจริงก็เหลือไล่แค่ตัวเดียวคือ y

ทั้งสองสมการมี n² ช่อง ช่องละงาน n ครั้ง จึงเหลือ O(n³) ดีขึ้นมากแต่ยังไม่พอ

แล้วยังต้องต่ออีกชั้น เพราะโจทย์ให้หยุดกลางทางได้

f ตอบได้แค่กรณี "กวาดช่วงนี้เกลี้ยง" แต่โจทย์อนุญาตให้เหลือหนังสือคาไว้ (อย่างกอง D ในเกมข้างบนที่ต้องยอมทิ้งไว้หนึ่งเล่ม) จึงต้องมี DP อีกชั้นมาเลือกว่าจะกวาดช่วงไหนบ้าง โดยช่วงที่เลือกห้ามซ้อนกัน ให้ g[k] คือแต้มสูงสุดเมื่อดูหนังสือ k เล่มแรก

ก่อนอ่านสมการนี้ ต้องรู้ก่อนว่าสองตารางนับของไม่เหมือนกัน g นับเป็นจำนวนเล่ม ส่วน f นับเป็นตำแหน่งเล่ม ที่เริ่มจาก 0 พอ g[i] แปลว่าจัดการเล่มแรก i เล่มเสร็จแล้ว เล่มถัดไปที่ยังไม่ถูกแตะจึงอยู่ที่ตำแหน่ง i พอดี เลข i ตัวเดียวเลยทำสองหน้าที่พร้อมกัน คือเป็นทั้งจำนวนเล่มที่จบไปแล้ว และตำแหน่งเริ่มของช่วงใหม่ ส่วนปลายช่วงคือเล่มที่ k ซึ่งอยู่ตำแหน่ง k-1 ช่วงที่กำลังจะกวาดจึงเขียนว่า f[i][k-1]

• กิ่ง g[k-1] คือปล่อยเล่มที่ k คาไว้บนชั้น ไม่เอามาคิดแต้มเลย แต้มจึงเท่ากับของเล่มแรก k-1 เล่มเป๊ะ ๆ กิ่งนี้ใช้ได้ทุกกรณีโดยไม่มีเงื่อนไข และมันเป็นกิ่งเดียวที่ทำให้ "หยุดกลางทาง" เกิดขึ้นได้ ถ้าตัดกิ่งนี้ออก ทุกเล่มจะถูกบังคับให้ไปอยู่ในช่วงที่กวาดเกลี้ยงช่วงใดช่วงหนึ่ง ซึ่งเข้มกว่าที่โจทย์ขอไว้
• กิ่ง g[i] + f[i][k-1] คือปิดท้ายด้วยการกวาดช่วง [i .. k-1] ให้เกลี้ยง เล่มแรก i เล่มคิดจบไปแล้วใน g[i] ที่บวกเข้ามาจึงเป็นแต้มของช่วงใหม่ล้วน ๆ ซึ่ง f ตอบไว้ให้แล้ว ช่วงใหม่จ่อกับของเก่าพอดี ไม่มีเล่มไหนถูกนับสองครั้งและไม่มีเล่มไหนหลุดหาย กิ่งนี้มีอยู่เฉพาะช่วงที่กวาดเกลี้ยงได้จริง ช่วงที่ทำไม่ได้ f จะคืนค่าว่าเป็นไปไม่ได้ แล้วกิ่งนี้ก็หายไปเอง (โค้ดในเฉลยข้างล่างเช็คตรงนี้ด้วย v != NEG)

เพราะกิ่งแรกไม่มีเงื่อนไข g[k] จึงมีค่าเสมอ ไม่มีช่องไหนตอบว่าทำไม่ได้ และคำตอบของโจทย์คือ g[n] ที่อ่านว่า "ดูหนังสือครบทุกเล่มแล้ว" ไม่ได้อ่านว่า "กวาดหนังสือออกครบทุกเล่มแล้ว"

ชั้นนี้เพิ่มงานมาอีก n² ครั้ง ซึ่งไม่ใช่ตัวปัญหา ตัวปัญหาคือ f กับ t ที่อยู่ข้างล่าง

บิลค่าใช้จ่าย ตอนที่ทำให้รู้ว่าลิมิตคือคำใบ้

เอาขอบเขตจริงของโจทย์มาแทน แล้วเทียบกับเฉลยที่เดินตารางเดียวแบบข้างบน

// DP บนช่วง: ทางที่คนคิดถึงก่อน ถูกต้องแต่แพงเกินลิมิตของโจทย์ข้อนี้
// f[i][j] = แต้มสูงสุดถ้า "เก็บกวาดช่วง [i..j] ออกให้หมดทั้งช่วง"
// t[i][y] = ตัวช่วย: เลือกบวกสองเล่มคือ i กับ x แล้วเคลียร์ของแทรกจนพร้อมจะเจอ y
#include <bits/stdc++.h>
using namespace std;

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

    const long long NEG = LLONG_MIN / 4;
    vector<vector<long long>> f(n + 1, vector<long long>(n + 1, NEG));
    vector<vector<long long>> t(n + 1, vector<long long>(n + 1, NEG));
    // ช่วงว่างถือว่าเคลียร์แล้ว ได้ 0 แต้ม
    auto F = [&](int i, int j) -> long long {
        if (i > j) return 0;
        if (i < 0 || j >= n) return NEG;
        return f[i][j];
    };

    for (int len = 3; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            // เติม t[i][y] ที่ยังไม่เคยคิด (y = j) ค่าที่ y < j คิดไปแล้วในรอบก่อน
            for (int y = i + 2; y <= j; y++) {
                if (t[i][y] != NEG) continue;
                long long best = NEG;
                for (int x = i + 1; x < y; x++) {
                    long long l = F(i + 1, x - 1), m = F(x + 1, y - 1);
                    if (l == NEG || m == NEG) continue;
                    best = max(best, (long long)a[i] + a[x] + l + m);
                }
                t[i][y] = best;
            }
            long long best = NEG;
            for (int y = i + 2; y <= j; y++) {
                long long rest = F(y + 1, j);
                if (t[i][y] == NEG || rest == NEG) continue;
                best = max(best, t[i][y] - a[y] + rest);
            }
            f[i][j] = best;
        }
    }

    // หยุดหยิบกลางทางได้ จึงต้องต่ออีกชั้นว่าจะเอาช่วงไหนมาต่อกันบ้าง
    vector<long long> g(n + 1, 0);
    for (int k = 1; k <= n; k++) {
        g[k] = g[k - 1];
        for (int i = 0; i < k; i++) {
            long long v = F(i, k - 1);
            if (v != NEG) g[k] = max(g[k], g[i] + v);
        }
    }
    printf("%lld\n", g[n]);
    return 0;
}

บทเรียนที่ได้ · state ที่ดีคือ state ที่กล้าลืม

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

การกล้าลืมตำแหน่งนั้นถูกต้องเพราะโครงสร้างที่พิสูจน์ไว้ในเฉลยตอนที่ 3 การจับคู่ของการหยิบต้องซ้อนกันเป็นชั้น ไขว้กันไม่ได้ เมื่อไขว้ไม่ได้ ลบตัวถัดไปก็ต้องไปปิดจ๊อบกับบวกสองตัวล่าสุดเสมอ เราจึงไม่ต้องจำชื่อของมัน จำแค่จำนวนก็พอ มิติของตารางเลยยุบจากสองตำแหน่งเหลือตำแหน่งเดียวบวกตัวนับหนึ่งตัว และหน่วยความจำยุบจาก 32,000,000 ไบต์เหลือ 32,016 ไบต์ (หน่วยเดียวกัน คือช่องละ 8 ไบต์)

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

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

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

แหล่งที่มา

โจทย์ต้นฉบับเป็นภาษาไทย ผมเรียบเรียงคำอธิบายใหม่ด้วยคำตัวเอง ส่วนวิธีคิดและโค้ดเป็นของผมเอง ตรวจกับตัวอย่างของโจทย์และการสุ่มเทียบแล้ว

1. โจทย์ "หยิบหนังสือ" จากคลังโจทย์ programming.in.th ผู้แต่งโจทย์ วรภัทร จรางกูล (สืบค้น 26 สิงหาคม 2026)
2. โจทย์ต้นทางระบุว่าดัดแปลงจากข้อสอบพี่ช่วยน้อง โรงเรียนมหิดลวิทยานุสรณ์ พ.ศ. 2552
3. ที่มาของชื่อ dynamic programming จากคำบอกเล่าของ Richard Bellman ในอัตชีวประวัติ Eye of the Hurricane: An Autobiography (1984)