ปูพื้นฐาน

แบ่งครึ่งเร่งดีพี: ตัดงานของทั้งแถวทิ้ง ด้วยคำตอบของช่องเดียวตรงกลาง

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

ปัญหาที่บทนี้แก้

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

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

สูตรที่ทุกคนเขียนได้ กับตัวเลขที่ทำให้มันตกรอบ

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

ตรงนี้ C(m, i) คือค่าใช้จ่ายของกองที่รับของชิ้นที่ m ถึง i ส่วน dp[j-1][m-1] คือของที่เหลือข้างหน้าซึ่งจัดไปแล้ว j-1 กอง

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

ลองเอง · วางที่กั้นคอกด้วยมือ

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

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

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

ของชิ้นเดียวที่เปลี่ยนทุกอย่าง คือจุดตัดที่ดีที่สุด

ตั้งชื่อให้มันก่อน เรียกว่า opt(j, i)

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

ทีนี้ลองพิมพ์ opt ของทุกช่องออกมาดู นี่คือของจริงจากม้าแปดตัวข้างบน

นั่นคือข้อเท็จจริงทั้งหมดที่ท่านี้ต้องการ เขียนเป็นสัญลักษณ์ได้แบบนี้

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

ทำไมรู้แค่นี้แล้วเร็วขึ้นได้

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

กุญแจอยู่ที่การเลิกเดินจากซ้ายไปขวา แล้วหันไปทำช่องตรงกลางก่อน

• สมมติจะเติมช่วง 1..8 เริ่มที่ช่องกลางคือ i = 4 ก่อน
• ตอนนี้ยังไม่รู้อะไรเลย ก็ต้องไล่ m ทั้ง 4 ค่า สมมติว่าได้ opt = 3
• ทันทีที่รู้ว่า opt(4) = 3 ช่อง 1..3 ทั้งหมดมี opt ไม่เกิน 3 และช่อง 5..8 ทั้งหมดมี opt ไม่น้อยกว่า 3 ค่าเดียวที่เพิ่งคำนวณไป ตัดพื้นที่ค้นหาของอีกเจ็ดช่องพร้อมกัน
• แล้วก็ทำแบบเดิมกับแต่ละครึ่ง ครึ่งซ้ายมีหน้าต่างของตัวเอง ครึ่งขวาก็มีของตัวเอง

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

เดินให้ดูทีละขั้น

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

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

ทำไมถึงเหลือแค่ n log n ต่อชั้น

การเรียกซ้ำแบ่งครึ่งไปเรื่อย ๆ จึงลึกประมาณ log n ชั้น คำถามที่เหลือคือในหนึ่งชั้นความลึก งานรวมเป็นเท่าไร

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

รวมความยาวหน้าต่างทั้งชั้นจึงไม่เกิน n บวกจำนวนช่วงในชั้นนั้น ซึ่งชั้นที่ลึก d มีช่วงไม่เกิน 2^d ช่วง แต่ก็ไม่เกิน n อยู่ดี งานต่อชั้นความลึกจึงเป็น O(n) คูณด้วยความลึก log n และคูณด้วยจำนวนชั้นของดีพี k ได้เป็น O(k · n log n)

แม่แบบที่ลอกไปใช้ได้ทุกข้อ

ทั้งบทเหลือโค้ดชุดเดียว เปลี่ยนแค่ C กับการอ่านอินพุต

// แม่แบบท่าแบ่งครึ่ง ใช้ได้ทุกข้อที่ dp[j][i] = min ของ dp[j-1][m-1] + C(m, i)
// เปลี่ยนแค่ฟังก์ชัน C กับการอ่านอินพุต ที่เหลือลอกทั้งก้อน
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, k;
vector<ll> dpBefore, dpCur;

ll C(int l, int r);              // ค่าใช้จ่ายของกลุ่มที่รับตัวที่ l..r

const ll INF = LLONG_MAX / 4;

// เติม dpCur[l..r] โดยรู้ว่าจุดตัดที่ดีที่สุดของช่วงนี้อยู่ใน [optl, optr]
void compute(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) / 2;
    pair<ll, int> best = {INF * 2, -1};
    for (int m = optl; m <= min(mid, optr); m++)
        best = min(best, {dpBefore[m - 1] + C(m, mid), m});
    dpCur[mid] = best.first;
    int opt = best.second;
    compute(l, mid - 1, optl, opt);      // ครึ่งซ้าย จุดตัดไม่เกิน opt
    compute(mid + 1, r, opt, optr);      // ครึ่งขวา จุดตัดไม่น้อยกว่า opt
}

ll solve() {
    dpBefore.assign(n + 1, INF);
    dpCur.assign(n + 1, INF);
    dpBefore[0] = 0;                 // ชั้นที่ 0 ครอบได้แค่ของศูนย์ตัว

    for (int j = 1; j <= k; j++) {
        fill(dpCur.begin(), dpCur.end(), INF);
        compute(1, n, 1, n);
        swap(dpBefore, dpCur);       // dpCur[0] ยังเป็น INF ซึ่งถูกแล้ว เพราะกลุ่มว่างไม่ได้
    }
    return dpBefore[n];
}

ก่อนใช้ท่านี้ ต้องรู้ได้ยังไงว่าใช้ได้

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

เงื่อนไขที่พิสูจน์ได้และใช้ได้กว้างที่สุดชื่อ อสมการสี่เหลี่ยม (quadrangle inequality อ่านว่า "ควอดแรงเกิล อิเนอควอลิตี") สำหรับทุก a ≤ b ≤ c ≤ d ต้องได้ว่า

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

// เครื่องมือที่ควรเขียนก่อนเชื่อว่าใช้ท่านี้ได้: พิมพ์แถว opt ออกมาดูเลย
// ถ้าเลขในแถวไหนลดลงแม้แต่ครั้งเดียว แปลว่าท่าแบ่งครึ่งใช้กับโจทย์นี้ไม่ได้
for (int j = 1; j <= k; j++) {
    printf("opt ชั้น %d:", j);
    int last = 0;
    for (int i = 1; i <= n; i++) {
        printf(" %d", opt[j][i]);
        if (opt[j][i] < last) printf("(ถอยหลัง!)");
        last = opt[j][i];
    }
    printf("\n");
}

ถ้าฝืนใช้กับโจทย์ที่ไม่เข้าเงื่อนไข จะพังยังไง

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

แถว opt ของชั้นที่ 2 ออกมาเป็น ·, 2, 3, 2 ซึ่งถอยหลังที่ช่องสุดท้าย ผลคือดีพีสองลูปตอบ 7 แต่ท่าแบ่งครึ่งตอบ 8

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

โจทย์ฝึกข้อที่ 1 · ม้าสองสี

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

อ่านตัวอย่างนี้ยังไง

บรรทัดแรกบอกว่ามีม้า 6 ตัว และมีคอกให้ 3 คอก อีก 6 บรรทัดที่เหลือคือสีของม้า เรียงจากตัวซ้ายสุดไปขวาสุด ตัวเลข 1 คือดำ 0 คือขาว ชุดนี้จึงอ่านได้ว่า ดำ ดำ ขาว ดำ ขาว ดำ

สิ่งที่เราเลือกได้มีอย่างเดียวคือจะวางที่กั้นตรงไหน ม้า 6 ตัวมีช่องว่างระหว่างตัวอยู่ 5 ช่อง และต้องวางที่กั้น 2 อัน แบ่งได้ทั้งหมด 10 แบบ เอาต์พุตคือค่าที่ต่ำที่สุดในบรรดา 10 แบบนั้น ซึ่งชุดนี้คือ 2

คอกที่ 3 เป็นคอกเดียวที่ต้องจ่าย เพราะในคอกนั้นมีม้าดำ 2 ตัว และม้าขาว 1 ตัว จับคู่ข้ามสีกันได้ 2 คูณ 1 เท่ากับ 2 คู่ ส่วนอีกสองคอกมีสีเดียวล้วน จึงไม่มีคู่ต่างสีให้จับเลย ค่าเป็นศูนย์

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

เฉลยข้อที่ 1

โค้ดข้อที่ 1

// ม้าสองสี: แบ่งม้า n ตัวที่เรียงอยู่แล้วเป็น k คอก ให้ผลรวม (ดำ x ขาว) ของทุกคอกน้อยที่สุด
// อินพุต: n k แล้วตามด้วย n บรรทัด บรรทัดละ 1 (ดำ) หรือ 0 (ขาว)
// เอาต์พุต: ค่าความไม่พอใจรวมที่น้อยที่สุด
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, k;
vector<int> pb;                 // pb[i] = จำนวนม้าดำในตัวที่ 1..i
vector<ll> dpBefore, dpCur;

// ค่าใช้จ่ายของคอกที่รับม้าตัวที่ l..r (นับจาก 1)
ll C(int l, int r) {
    ll b = pb[r] - pb[l - 1];
    ll w = (r - l + 1) - b;
    return b * w;
}

const ll INF = LLONG_MAX / 4;

// เติม dpCur[l..r] โดยรู้ว่าจุดตัดที่ดีที่สุดของช่วงนี้อยู่ใน [optl, optr]
void compute(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) / 2;
    pair<ll, int> best = {INF * 2, -1};
    for (int m = optl; m <= min(mid, optr); m++)     // คอกสุดท้ายรับม้าตัวที่ m..mid
        best = min(best, {dpBefore[m - 1] + C(m, mid), m});
    dpCur[mid] = best.first;
    int opt = best.second;
    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

int main() {
    if (scanf("%d %d", &n, &k) != 2) return 0;
    pb.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) { int c; scanf("%d", &c); pb[i] = pb[i - 1] + c; }

    dpBefore.assign(n + 1, INF);
    dpCur.assign(n + 1, INF);
    dpBefore[0] = 0;                 // ชั้นที่ 0 คือยังไม่เปิดคอกเลย ครอบได้แค่ของศูนย์ตัว

    for (int j = 1; j <= k; j++) {
        fill(dpCur.begin(), dpCur.end(), INF);
        compute(1, n, 1, n);
        swap(dpBefore, dpCur);       // dpCur[0] ยังเป็น INF ซึ่งถูกแล้ว เพราะคอกว่างไม่ได้
    }
    printf("%lld\n", dpBefore[n]);
    return 0;
}

โจทย์ฝึกข้อที่ 2 · คิวขึ้นกระเช้า

มีคน n คนต่อคิวอยู่ กระเช้ามาทีละคัน รวม k คัน คันแรกรับคนหัวคิวไป q1 คน คันต่อไปรับหัวคิวที่เหลือไป q2 คน ไปเรื่อย ๆ ทุกคันต้องมีคนอย่างน้อยหนึ่งคน โจทย์ให้ตาราง u ขนาด n × n มาด้วย โดย u[i][j] คือความไม่คุ้นเคยระหว่างคนที่ i กับคนที่ j ความไม่คุ้นเคยของกระเช้าคันหนึ่งคือผลรวมของทุกคู่คนที่นั่งคันเดียวกัน ขอผลรวมของทุกคันที่น้อยที่สุด

อ่านตัวอย่างนี้ยังไง

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

ที่ต้องระวังคือคิวสลับที่ไม่ได้ กระเช้าคันแรกรับคนหัวคิวติดกันไปเท่านั้น เราจึงเลือกได้แค่ว่าคันแรกจะรับไปกี่คน ที่เหลือตามมาเอง สำหรับ 4 คน 2 คัน จึงมีทางเลือกแค่ 3 แบบ

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

เฉลยข้อที่ 2

โค้ดข้อที่ 2

// Ciel and Gondolas: แบ่งคิว n คนเป็น k กลุ่มติดกัน ให้ผลรวมความไม่คุ้นเคยในกลุ่มน้อยที่สุด
// อินพุต: n k แล้วตารางความไม่คุ้นเคย n x n   เอาต์พุต: ผลรวมที่น้อยที่สุด
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, k;
vector<vector<int>> S;          // S[i][j] = ผลรวมสี่เหลี่ยมมุมบนซ้าย (1,1) ถึง (i,j)
vector<ll> dpBefore, dpCur;

// ความไม่คุ้นเคยรวมของกลุ่มที่รับคนที่ l..r  คือครึ่งหนึ่งของสี่เหลี่ยม เพราะตารางสมมาตร
ll C(int l, int r) {
    return (ll)(S[r][r] - S[l - 1][r] - S[r][l - 1] + S[l - 1][l - 1]) / 2;
}

const ll INF = LLONG_MAX / 4;

// เติม dpCur[l..r] โดยรู้ว่าจุดตัดที่ดีที่สุดของช่วงนี้อยู่ใน [optl, optr]
void compute(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) / 2;
    pair<ll, int> best = {INF * 2, -1};
    for (int m = optl; m <= min(mid, optr); m++)
        best = min(best, {dpBefore[m - 1] + C(m, mid), m});
    dpCur[mid] = best.first;
    int opt = best.second;
    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

int main() {
    if (scanf("%d %d", &n, &k) != 2) return 0;
    S.assign(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int v; scanf("%d", &v);
            S[i][j] = v + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
        }

    dpBefore.assign(n + 1, INF);
    dpCur.assign(n + 1, INF);
    dpBefore[0] = 0;                 // ชั้นที่ 0 คือยังไม่เปิดกลุ่มเลย ครอบได้แค่ของศูนย์ตัว

    for (int j = 1; j <= k; j++) {
        fill(dpCur.begin(), dpCur.end(), INF);
        compute(1, n, 1, n);
        swap(dpBefore, dpCur);       // dpCur[0] ยังเป็น INF ซึ่งถูกแล้ว เพราะกลุ่มว่างไม่ได้
    }
    printf("%lld\n", dpBefore[n]);
    return 0;
}

โจทย์ฝึกข้อที่ 3 · ตัดอาเรย์ให้คู่ซ้ำน้อยที่สุด

ให้อาเรย์ยาว n ตัดให้ติดกันเป็น k ช่วง ค่าใช้จ่ายของช่วงหนึ่งคือจำนวนคู่ตำแหน่งในช่วงนั้นที่ค่าเท่ากัน ขอผลรวมที่น้อยที่สุด

อ่านตัวอย่างนี้ยังไง

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

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

ที่กั้นทำหน้าที่เดียวคือตัดคู่ให้ขาดจากกัน คู่ไหนมีที่กั้นคั่นอยู่ตรงกลาง คู่นั้นไม่ต้องจ่าย งานของเราคือวางที่กั้น 2 อันให้ตัดคู่ได้มากที่สุด

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

เฉลยข้อที่ 3

โค้ดข้อที่ 3

// Yet Another Minimization Problem: แบ่งอาเรย์ n ตัวเป็น k ช่วงติดกัน
// ค่าใช้จ่ายของช่วงคือจำนวนคู่ตำแหน่งในช่วงนั้นที่ค่าเท่ากัน ให้ผลรวมน้อยที่สุด
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, k;
vector<int> a, cnt;
vector<ll> dpBefore, dpCur;
int curL = 1, curR = 0;
ll curCost = 0;

void addAt(int i) { curCost += cnt[a[i]]++; }      // ตัวใหม่จับคู่กับตัวที่ค่าเดียวกันซึ่งอยู่ในหน้าต่างแล้ว
void remAt(int i) { curCost -= --cnt[a[i]]; }

// ค่าใช้จ่ายของช่วง l..r ได้จากการเลื่อนขอบหน้าต่างเดิม ขยายก่อนแล้วค่อยหด
ll C(int l, int r) {
    while (curR < r) addAt(++curR);
    while (curL > l) addAt(--curL);
    while (curR > r) remAt(curR--);
    while (curL < l) remAt(curL++);
    return curCost;
}

const ll INF = LLONG_MAX / 4;

// เติม dpCur[l..r] โดยรู้ว่าจุดตัดที่ดีที่สุดของช่วงนี้อยู่ใน [optl, optr]
void compute(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) / 2;
    pair<ll, int> best = {INF * 2, -1};
    for (int m = optl; m <= min(mid, optr); m++)
        best = min(best, {dpBefore[m - 1] + C(m, mid), m});
    dpCur[mid] = best.first;
    int opt = best.second;
    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

int main() {
    if (scanf("%d %d", &n, &k) != 2) return 0;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    cnt.assign(n + 2, 0);

    dpBefore.assign(n + 1, INF);
    dpCur.assign(n + 1, INF);
    dpBefore[0] = 0;                 // ชั้นที่ 0 คือยังไม่เปิดช่วงเลย ครอบได้แค่ของศูนย์ตัว

    for (int j = 1; j <= k; j++) {
        fill(dpCur.begin(), dpCur.end(), INF);
        compute(1, n, 1, n);
        swap(dpBefore, dpCur);       // dpCur[0] ยังเป็น INF ซึ่งถูกแล้ว เพราะช่วงว่างไม่ได้
    }
    printf("%lld\n", dpBefore[n]);
    return 0;
}

บักที่ติดมากับโค้ดต้นแบบที่ทุกคนลอก

โค้ดต้นแบบที่หาเจอทั่วไปเขียนชั้นแรกด้วยมือ แล้วปล่อยให้ dp_before[0] เป็นศูนย์ค้างไว้ ทุกชั้น ความหมายของมันคือ "เอาของศูนย์ชิ้นไปจัดเป็นหลายกอง ได้ค่าศูนย์" ซึ่งแปลว่ายอมให้กองว่าง

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

แต่พอค่าใช้จ่ายมีค่าเปิดกอง เรื่องเปลี่ยนทันที ลองให้ C(l, r) เท่ากับ 10 บวกจำนวนสมาชิก แล้วสั่งแบ่งของ 6 ชิ้นเป็น 3 กอง

ทางแก้คือให้ชั้นที่ศูนย์เป็นชั้นเดียวที่ dp[0] เป็นศูนย์ แล้ววนตั้งแต่ชั้นที่ 1 ไม่ใช่เขียนชั้นที่ 1 ด้วยมือ ซึ่งเป็นสิ่งที่แม่แบบข้างบนทำอยู่แล้ว

ตัวตรวจที่ควรเขียนคู่กันทุกครั้ง

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

// ตัวตรวจอิสระ: ดีพีสองลูปตรงไปตรงมา ไล่จุดตัดทุกจุดจริง
// ไม่มีการแบ่งครึ่ง ไม่มีข้ออ้างว่า opt ไม่ถอยหลัง จึงไม่ได้ทดสอบข้ออ้างของตัวจริงเลย
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll C(int l, int r);              // ใส่ค่าใช้จ่ายของโจทย์ที่กำลังตรวจ

int main() {
    int n, k; if (scanf("%d %d", &n, &k) != 2) return 0;
    // ... อ่านอินพุตของโจทย์นั้น ...
    const ll INF = LLONG_MAX / 4;
    vector<vector<ll>> dp(k + 1, vector<ll>(n + 1, INF));
    dp[0][0] = 0;
    for (int j = 1; j <= k; j++)
        for (int i = 1; i <= n; i++)
            for (int m = 1; m <= i; m++)
                if (dp[j - 1][m - 1] < INF)
                    dp[j][i] = min(dp[j][i], dp[j - 1][m - 1] + C(m, i));
    printf("%lld\n", dp[k][n]);
    return 0;
}

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

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

ที่มาและอ่านต่อ

1. cp-algorithms, "Divide and Conquer DP" ต้นทางของสูตร โค้ดแม่แบบ และรายชื่อโจทย์ฝึกทั้งหมดในบทนี้ cp-algorithms.com
2. Timus Online Judge ปัญหา 1167 Bicolored Horses คือโจทย์ข้อที่ 1 acm.timus.ru
3. Codeforces 321E Ciel and Gondolas คือโจทย์ข้อที่ 2 codeforces.com
4. Codeforces 868F Yet Another Minimization Problem คือโจทย์ข้อที่ 3 codeforces.com