Агуулгыг алгасах

Хуваа ба ялагтун динамик программчлал

Хуваа ба ялагтун бол динамик программчлалын оптимизаци юм.

Урьдчилсан нөхцөл

Зарим динамик программчлалын бодлого дараах хэлбэрийн рекуррент хамааралтай байдаг:

$$ dp(i, j) = \min_{0 \leq k \leq j} \\{ dp(i - 1, k - 1) + C(k, j) \\} $$

энд $C(k, j)$ нь өртгийн функц бөгөөд $j \lt 0$ үед $dp(i, j) = 0$.

$0 \leq i \lt m$ ба $0 \leq j \lt n$, мөн $C$-г тооцоолоход $O(1)$ хугацаа зарцуулагдана гэж үзье. Тэгвэл дээрх рекуррент хамаарлыг шууд тооцоолох нь $O(m n^2)$ болно. $m \times n$ төлөв байх ба төлөв бүрд $n$ шилжилт байна.

Дээрх илэрхийллийг хамгийн бага болгох $k$-ийн утгыг $opt(i, j)$ гэе. Өртгийн функц дөрвөн өнцөгтийн тэнцэтгэл бишийг хангадаг гэж үзвэл бид бүх $i, j$-ийн хувьд $opt(i, j) \leq opt(i, j + 1)$ болохыг харуулж болно. Үүнийг монотон байдлын нөхцөл гэж нэрлэдэг. Тэгвэл бид хуваа ба ялагтун DP-г хэрэглэж болно. Тогтмол $i$-ийн хувьд оновчтой "хуваах цэг" $j$ нэмэгдэх тусам нэмэгдэнэ.

Энэ нь бидэнд бүх төлвийг илүү үр ашигтай бодох боломж олгоно. Бид ямар нэг тогтмол $i$ ба $j$-ийн хувьд $opt(i, j)$-г тооцоолсон гэж бодъё. Тэгвэл дурын $j' < j$-ийн хувьд бид $opt(i, j') \leq opt(i, j)$ гэдгийг мэднэ. Энэ нь $opt(i, j')$-г тооцоолохдоо бид тийм олон хуваах цэг авч үзэх шаардлагагүй гэсэн үг!

Ажиллах хугацааг хамгийн бага болгохын тулд бид хуваа ба ялагтуны цаад санааг хэрэглэнэ. Эхлээд $opt(i, n / 2)$-г тооцоол. Дараа нь $opt(i, n / 4)$-г (энэ нь $opt(i, n / 2)$-ээс бага буюу тэнцүү гэдгийг мэдэж) ба $opt(i, 3 n / 4)$-г (энэ нь $opt(i, n / 2)$-ээс их буюу тэнцүү гэдгийг мэдэж) тооцоол. $opt$-ийн доод ба дээд заагийг рекурсивээр хянаснаар бид $O(m n \log n)$ ажиллах хугацаанд хүрнэ. Хэрэгжүүлэлтийн нарийн ширийнийг доорх кодоос үзнэ үү.

Хуваа ба ялагтуны complexity-г батлахын тулд эхлээд рекурсид $O(\log{n})$ түвшин байгааг тэмдэглэе. Түвшин бүрд $O(n)$ алхам хийгдэж байна гэж бид батлана. $k$-р түвшин дэх $\text{opt}$ интервалуудын (кодод $optl$ ба $optr$ гэж тэмдэглэсэн) нийт уртыг $S_k$ гэе, мөн $k$ түвшнээс $x$ урттай интервалыг хуваах бүрд гарсан интервал(ууд)ын нийт урт хамгийн ихдээ $x + 1$ байхыг ажигла. Түүнчлэн $k$ түвшинд хамгийн ихдээ $2^k$ хуваалт хийгдэх тул бид $S_{k + 1} \leq S_k + 2^k$ болно. $S_0 = n$-тэйгээр заагийг индукцээр хэрэглэвэл түвшин $k$ бүрийн хувьд

$$ S_k < n + 2^k \in O(n). $$

болно. Тиймээс хуваа ба ялагтун бүрийн complexity нь $O(n\log{n})$, бүхэл DP тооцооллын complexity нь $O(mn\log{n})$ болно.

Generic implementation

Even though implementation varies based on problem, here's a fairly generic template. The function compute computes one row $i$ of states dp_cur, given the previous row $i-1$ of states dp_before. It has to be called with compute(0, n-1, 0, n-1). The function solve computes m rows and returns the result.

int m, n;
vector<long long> dp_before, dp_cur;

long long C(int i, int j);

// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    pair<long long, int> best = {LLONG_MAX, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k});
    }

    dp_cur[mid] = best.first;
    int opt = best.second;

    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

long long solve() {
    dp_before.assign(n,0);
    dp_cur.assign(n,0);

    for (int i = 0; i < n; i++)
        dp_before[i] = C(0, i);

    for (int i = 1; i < m; i++) {
        compute(0, n - 1, 0, n - 1);
        dp_before = dp_cur;
    }

    return dp_before[n - 1];
}

Анхаарах зүйлс

Хуваа ба ялагтун DP бодлогын хамгийн том бэрхшээл бол $opt$-ийн монотон байдлыг батлах явдал юм. Энэ нь үнэн байх нэг онцгой тохиолдол бол өртгийн функц дөрвөн өнцөгтийн тэнцэтгэл бишийг хангах, өөрөөр хэлбэл бүх $a \leq b \leq c \leq d$-ийн хувьд $C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$ байх үе юм. Олон хуваа ба ялагтун DP бодлогыг мөн Гүдгэр бүрхүүлийн аргаар (Convex Hull trick) бодож болох ба эсрэгээр нь. Хоёуланг нь мэдэж, ойлгох нь хэрэгтэй!

Дасгал бодлогууд

Ашигласан материал