ปูพื้นฐาน

DP ที่สถานะคือความจำล่าสุด: เก็บอดีตให้น้อยที่สุดเท่าที่อนาคตยังต้องใช้

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

อาการ · ตัวเลขเดียวต่อหนึ่งคำนำหน้า เก็บได้ไม่พอ

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

ท่ามาตรฐานของ DP คือให้ dp[i] เป็นคะแนนดีที่สุดเมื่อดูของ i ชิ้นแรก แล้วเดินไปข้างหน้าทีละชิ้น ลองใช้กับแถวสั้น ๆ แค่สามชิ้นคือ 5 5 100 ดู

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

แต่คำตอบจริงของแถวนี้คือ 105 ซึ่งได้จากการเลือกชิ้นที่ 1 กับ 3 นั่นคือยอมทิ้งชิ้นที่สอง ทั้งที่มันทำให้คะแนนของคำนำหน้าลดลงจาก 10 เหลือ 5

ลองเอง · เลือกของให้ได้แต้มมากที่สุด

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

ทางออก · จดสภาพลงไปในสถานะด้วย

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

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

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

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

บรรทัดบนคือข้ามของชิ้นนี้ ช่วงที่เลือกติดกันขาดทันที ไม่ว่าก่อนหน้าจะค้างมากี่ชิ้นก็ตกมาที่ศูนย์เหมือนกันหมด บรรทัดล่างคือเก็บของชิ้นนี้ ช่วงยาวขึ้นหนึ่ง ซึ่งทำได้เฉพาะตอนที่ค้างอยู่ไม่ถึงสองชิ้น

เดินตารางให้ดูหนึ่งแถว

เอาแถว 5 5 100 1 8 9 มาเดินจริง แต่ละแถวของตารางคือหลังตัดสินใจของชิ้นนั้นเสร็จแล้ว ช่องที่เป็นจุดคือสถานะที่ยังไปไม่ถึง

แผนที่ดีที่สุดคือเก็บชิ้นที่ 1, 3, 5, 6 รวม 122 คะแนน สังเกตแถวที่เขียนว่า 2. ค่า 5 สองช่องซ้ายยังเก็บ 5 ไว้ ทั้งที่ช่องขวาสุดของแถวเดียวกันมี 10 ซึ่งมากกว่า ถ้าตารางมีคอลัมน์เดียว เลข 10 จะกลืนที่เหลือไปหมดตั้งแต่ตรงนั้น แล้วของชิ้นที่ 3 ที่มีค่า 100 ก็จะเก็บไม่ได้ ทั้งที่แถวถัดมาบอกชัดว่าเลข 5 คือตัวที่พาไปถึง 105

ด่านที่สาม · สถานะมีได้กี่แบบ

สองข้อสอบข้างบนบอกว่าอะไรใช้เป็นสถานะได้ แต่ไม่ได้บอกว่ามันคุ้ม เพราะของที่ผ่านสองข้อนั้นเสมอมีอยู่อย่างหนึ่ง คือ "จำอดีตทั้งหมดไว้เลย" ซึ่งพอไหมก็พอ ปิดตัวเองไหมก็ปิด แต่มันมีได้ถึง 2^n แบบ ซึ่งที่ n = 100,000 คือจำนวนที่เขียนลงกระดาษยังไม่ไหว

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

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

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

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

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> a(n);
    for (auto& x : a) scanf("%lld", &x);

    const long long NEG = LLONG_MIN / 4;          // เผื่อที่ให้บวกค่าเข้าไปโดยไม่ล้น
    vector<long long> cur(3, NEG), nxt(3);
    cur[0] = 0;                                   // ยังไม่เลือกอะไร ค้างศูนย์ชิ้น

    for (int i = 0; i < n; i++) {
        fill(nxt.begin(), nxt.end(), NEG);        // ต้องล้างก่อนทุกรอบ เพราะเราเขียนแบบผลัก
        for (int j = 0; j < 3; j++) {
            if (cur[j] == NEG) continue;          // สถานะนี้ยังไปไม่ถึง
            nxt[0] = max(nxt[0], cur[j]);                     // ข้ามชิ้นนี้ ช่วงที่เลือกติดกันขาด
            if (j < 2) nxt[j + 1] = max(nxt[j + 1], cur[j] + a[i]);  // เก็บชิ้นนี้ ช่วงยาวขึ้นหนึ่ง
        }
        cur = nxt;
    }

    printf("%lld\n", *max_element(cur.begin(), cur.end()));
    return 0;
}

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

อย่างที่สองคือค่า NEG ที่ใช้แทน "สถานะนี้ยังไปไม่ถึง" ซึ่งต้องแยกจากคะแนน 0 ให้ขาด เพราะ 0 เป็นคะแนนที่ถูกต้องได้ (ตอนยังไม่เลือกอะไรเลย) และต้องหารสี่ทิ้งไว้ด้วย เพราะเราจะเอาค่าไปบวกกับ a[i] ถ้าใช้ LLONG_MIN ตรง ๆ แล้วบวกเลขบวกเข้าไป มันจะล้นกลับไปเป็นค่าบวกมหาศาลแล้วชนะทุกอย่างในตาราง

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

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> a(n);
    for (auto& x : a) scanf("%lld", &x);

    long long best = LLONG_MIN;
    for (int m = 0; m < (1 << n); m++) {
        int run = 0;
        bool ok = true;
        long long s = 0;
        for (int i = 0; i < n; i++) {
            if (m >> i & 1) {
                run++; s += a[i];
                if (run >= 3) { ok = false; break; }
            } else run = 0;
        }
        if (ok) best = max(best, s);
    }
    printf("%lld\n", best);
}

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

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

ฝึกข้อ 1 ★☆☆☆☆ · ห้ามเว้นสามชิ้นติดกัน

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

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> c(n);
    for (auto& x : c) scanf("%lld", &x);

    const long long INF = LLONG_MAX / 4;
    vector<long long> cur(3, INF), nxt(3);
    cur[0] = 0;                                   // ยังไม่เว้นติดกันเลย

    for (int i = 0; i < n; i++) {
        fill(nxt.begin(), nxt.end(), INF);
        for (int j = 0; j < 3; j++) {
            if (cur[j] == INF) continue;
            nxt[0] = min(nxt[0], cur[j] + c[i]);           // เลือก ช่วงที่เว้นขาดทันที
            if (j < 2) nxt[j + 1] = min(nxt[j + 1], cur[j]);  // เว้น ช่วงยาวขึ้นหนึ่ง
        }
        cur = nxt;
    }

    printf("%lld\n", *min_element(cur.begin(), cur.end()));
    return 0;
}

ฝึกข้อ 2 ★★☆☆☆ · ทาสีที่ห้ามซ้ำสามช่องติดกัน

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;

int main() {
    long long n, k;
    scanf("%lld %lld", &n, &k);
    long long k1 = (k - 1) % MOD;

    // สถานะไม่ใช่ "ช่องล่าสุดเป็นสีอะไร" ซึ่งมี k แบบ
    // แต่เป็น "สองช่องล่าสุดสีเหมือนกันไหม" ซึ่งมีสองแบบ ไม่ว่า k จะใหญ่แค่ไหน
    long long diff = k % MOD, same = 0;           // ช่องแรกนับรวมไว้ฝั่ง diff
    for (long long i = 2; i <= n; i++) {
        long long nd = (diff + same) % MOD * k1 % MOD;   // ทาสีต่างจากช่องก่อนหน้า
        long long ns = diff;                             // ทาซ้ำได้ ก็ต่อเมื่อคู่ก่อนหน้าไม่ซ้ำ
        diff = nd;
        same = ns;
    }

    printf("%lld\n", (diff + same) % MOD);
    return 0;
}

ฝึกข้อ 3 ★★★☆☆ · เมื่อต้องจำค่าจริง ๆ

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;

int main() {
    long long n;
    scanf("%lld", &n);
    if (n == 1) { printf("3\n"); return 0; }      // ยังไม่มีคู่ให้จำ ตอบตรง ๆ

    // สถานะคือคู่ตัวอักษรสองตัวล่าสุด อัดเป็น p*3+q โดย q คือตัวล่าสุด
    vector<long long> cur(9, 0), nxt(9);
    for (int p = 0; p < 3; p++)
        for (int q = 0; q < 3; q++) cur[p * 3 + q] = 1;   // ความยาว 2 ทุกคู่ยังไม่ผิดกติกา

    for (long long i = 3; i <= n; i++) {
        fill(nxt.begin(), nxt.end(), 0);
        for (int p = 0; p < 3; p++)
            for (int q = 0; q < 3; q++) {
                long long v = cur[p * 3 + q];
                if (!v) continue;
                for (int r = 0; r < 3; r++) {
                    if (p == q && q == r) continue;            // สามตัวติดกันเหมือนกัน
                    if (p == 0 && q == 1 && r == 2) continue;  // abc
                    nxt[q * 3 + r] = (nxt[q * 3 + r] + v) % MOD;
                }
            }
        cur = nxt;
    }

    long long s = 0;
    for (int i = 0; i < 9; i++) s = (s + cur[i]) % MOD;
    printf("%lld\n", s);
    return 0;
}

ก้าวถัดไปของการบีบสถานะ · เมื่อสิ่งที่ต้องจำไม่ใช่ตัวเลขตัวเดียว

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

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

ท่าที่รับมือคือเก็บ n บิตนั้นเป็นจำนวนเต็มหนึ่งตัว โดยให้บิตที่ i แทนแถวที่ i จำนวนเต็มตัวนั้นเรียกว่าหน้ากากบิต (bitmask) และ DP ที่ใช้มันเป็นสถานะเรียกว่า DP บนหน้ากากบิต รูปที่เดินทีละช่อง ไม่ใช่ทีละคอลัมน์เต็ม เรียกเฉพาะลงไปอีกว่า broken profile

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

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

// DP บนหน้ากากบิต (broken profile): นับวิธีปูโดมิโน 1x2 ให้เต็มตาราง n แถว m คอลัมน์
// สถานะคือ "หน้ากากของช่องที่ยื่นล้ำมาจากคอลัมน์ก่อนหน้า" ซึ่งเป็นการบีบสถานะแบบเดียวกับบทนี้
// แต่สิ่งที่บีบไม่ใช่ตัวเลขเดียว มันคือแถวหนึ่งแถวที่เก็บเป็นบิต
// อินพุต: n m   เอาต์พุต: จำนวนวิธี หารเอาเศษด้วย 1e9+7
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    if (n > m) swap(n, m);                 // ให้ n เป็นด้านที่แคบกว่า หน้ากากจึงเล็กที่สุด
    int full = 1 << n;
    vector<long long> cur(full, 0), nxt(full, 0);
    cur[0] = 1;
    for (int col = 0; col < m; col++) {
        // เดินทีละคอลัมน์ ภายในคอลัมน์เดินทีละแถว
        for (int row = 0; row < n; row++) {
            fill(nxt.begin(), nxt.end(), 0);
            for (int mask = 0; mask < full; mask++) {
                long long v = cur[mask];
                if (v == 0) continue;
                if (mask >> row & 1) {
                    // ช่องนี้ถูกโดมิโนแนวนอนจากคอลัมน์ก่อนกินไปแล้ว ปิดบิตทิ้ง
                    nxt[mask ^ (1 << row)] = (nxt[mask ^ (1 << row)] + v) % MOD;
                } else {
                    // วางแนวนอน ยื่นไปคอลัมน์ถัดไป
                    nxt[mask | (1 << row)] = (nxt[mask | (1 << row)] + v) % MOD;
                    // วางแนวตั้ง กินช่องนี้กับช่องล่างในคอลัมน์เดียวกัน
                    if (row + 1 < n && !(mask >> (row + 1) & 1))
                        nxt[mask | (1 << (row + 1))] = (nxt[mask | (1 << (row + 1))] + v) % MOD;
                }
            }
            cur.swap(nxt);
        }
    }
    printf("%lld\n", cur[0] % MOD);
    return 0;
}

// ตัวตรวจอิสระของ broken profile: ไล่วางโดมิโนทุกวิธีด้วยการเรียกซ้ำบนช่องว่างแรกที่เจอ
// ไม่มีหน้ากากบิต ไม่มีการบีบสถานะ จึงไม่ได้ทดสอบข้ออ้างของท่านั้นเลย
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;

int n, m;
vector<vector<int>> used;
long long ways = 0;

void rec() {
    int r = -1, c = -1;
    for (int i = 0; i < n && r == -1; i++)
        for (int j = 0; j < m; j++)
            if (!used[i][j]) { r = i; c = j; break; }
    if (r == -1) { ways = (ways + 1) % MOD; return; }
    // วางแนวนอน
    if (c + 1 < m && !used[r][c + 1]) {
        used[r][c] = used[r][c + 1] = 1;
        rec();
        used[r][c] = used[r][c + 1] = 0;
    }
    // วางแนวตั้ง
    if (r + 1 < n && !used[r + 1][c]) {
        used[r][c] = used[r + 1][c] = 1;
        rec();
        used[r][c] = used[r + 1][c] = 0;
    }
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    used.assign(n, vector<int>(m, 0));
    rec();
    printf("%lld\n", ways % MOD);
    return 0;
}

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

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

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

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