97综合色色,久久大香蕉久久久久,色情网站一区二区

$\text{Part} 0$ 區(qū)間 $\text{dp}$ 是什么

關(guān)于動態(tài)規(guī)劃，其實(shí)說白了，就是一種遞推。當(dāng)我們解決大問題的時候，先把它分解為若干個子問題，再把它合并成當(dāng)前所需的結(jié)果。有點(diǎn)類似于遞歸的感覺，而遞歸會重復(fù)計(jì)算，普通 $\text{dp}$ 與記憶化搜索不會。

而區(qū)間 $\text{dp}$ ，就是這類問題中的一小類。在我們的分解操作時，它需要取任意區(qū)間的子問題結(jié)果。這類問題就叫做區(qū)間 $\text{dp}$ 。

對于大多數(shù)問題，區(qū)間 $\text{dp}$ 的架構(gòu)像這樣： $\text{dp}_{i,j}$ 被拆分為若干個 $\text{dp}_{l,r}$ （其中 $i \le l \le r \le j$ ），通過這些小區(qū)間計(jì)算出來的 $\text{dp}$ 值推算 $\text{dp}_{i,j}$ 。而 $\text{dp}$ 的兩個下標(biāo)代表一個區(qū)間的左端點(diǎn)與右端點(diǎn)。

具體問題具體分析，我們當(dāng)然需要結(jié)合問題來進(jìn)行學(xué)習(xí)。然而，區(qū)間 $\text{dp}$ 是有“套路”的，我們接下來把一個個花里胡哨的題目，透過現(xiàn)象去看它的本質(zhì)，然后把它們歸類為一個個套路。

$\text{Part}1$ 區(qū)間 $\text{dp}$ 架構(gòu)

通常，我們在做此類問題時，是由小區(qū)間推到為大區(qū)間。所以，我們要先枚舉小區(qū)間，再枚舉大區(qū)間，也就是 枚舉長度 。我們的 $\text{DP}$ 順序應(yīng)是這樣的：

image.png

偽代碼：

# 初始化 dp[i][i] 或 dp[i][i-1] 因題而異
for len=start to len=end len++ # 枚舉長度，start 和 end 分別為最短與最長的長度
    for i=1,j=len to j=n i++,j++ # 枚舉對應(yīng)長度的區(qū)間 (i,j)
        ( for k=i to k=j-1 k++ ) # 可能要枚舉中間點(diǎn)
            # 進(jìn)行 dp 操作

還有一種方法也是可以的，這篇文章中“關(guān)路燈”類題目也用了這種枚舉方法。（感謝金鉤爺 @SharpnessV）

首先我們看這種方法為什么不行：

for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
        // dp

假設(shè)我們程序運(yùn)行到 $i=1,j=5$ ，轉(zhuǎn)移到區(qū)間 $(1,3)$ 和 $(4,5)$ 的時候， $i=4,j=5$ 還沒有運(yùn)行。

我們得出結(jié)論：將左端點(diǎn)枚舉到 $i$ 的時候，比 $i$ 編號大的左端點(diǎn)一定要先枚舉到。所以一種新的做法出現(xiàn)了：

for(int i=n;i>=1;i--)
    for(int j=i;j<=n;j++)
        //dp

我們倒序枚舉左端點(diǎn)，就可以保證 $\text{dp}$ 順序正確。

$\text{Part}2$ 神奇的“套路”們

$\text{Part}2.1$ 石子合并類套路

此類問題，是常見的找中間點(diǎn) $k$ 分割的問題。

例 $2.1.1$ ZhimaOI #201 合并石子（未注冊 zhimaoi.cn 的人請注冊）

首先，對于一個區(qū)間 $(i,j)$ ，我們把這個區(qū)間內(nèi)所有石子給合并起來的上一步是啥？

將區(qū)間 $(i,k)$ 之間的所有石子全部合并（其中 $i\le k < j$ ）；
將區(qū)間 $(k+1,j)$ 之間的所有石子全部合并。

我們將這兩次合并的結(jié)果相加，再加上 $(i,j)$ 之間所有值的和即可。當(dāng)然，這個 $k$ 還得枚舉來選擇最優(yōu)的。

得轉(zhuǎn)移方程式： $\text{dp}_{i,j}=\operatorname{min}\{\text{dp}_{i,k}+\text{dp}_{k+1,j}+sum_{i,j}\} \quad(i\le k < j)$

例 $2.1.2$ Luogu P1880 [NOI1995] 石子合并

和例 $2.1.1$ 似乎是一樣的，然而它是一個環(huán)。我們的做法是 破環(huán)為鏈 ，將這個數(shù)列重復(fù)兩遍，取區(qū)間長度為 $n$ 的最值，這樣“環(huán)”就被我們考慮到了。

因?yàn)檫@題和上題相似，所以我只提供這題代碼。

例 $2.1.3$ Luogu P3146 [USACO16OPEN]248 G

和上述題目十分相似。切斷區(qū)間 $(i,j)$ 的 $k$ ，如果有 $\text{dp}_{i,k} = \text{dp}_{k+1,j}$ ，那么可以合并。得轉(zhuǎn)移方程式：

$\text{dp}_{i,j}=\max \{ \text{dp}_{i,k} +1\}\quad (i\le k < j,\text{dp}_{i,k}=\text{dp}_{k+1,j})$

例 $2.1.4$ HDU 4283 You Are the One

比較難的題目了。

在區(qū)間 $(i,j)$ 內(nèi)，我們首先確定這個 $i$ 的不高興的值。這玩意可以枚舉！

假設(shè)取中間點(diǎn) $k$ ，區(qū)間 $(i,k)$ 的人進(jìn)棧，顯然 $i$ 在這些人中最后一個出棧，等了 $k-i$ 個人，這些人的值我們已經(jīng)算好了。區(qū)間 $(k+1,j)$ 的人自然需要傻傻地等待 $(i,k)$ 之間的所有人，就是 $k-i+1$ 個人。這個值要加進(jìn)去。所以 $\text{dp}_{i,j}$ 是最小的 $\text{dp}_{i+1,k}+\text{dp}_{k+1,j}+cost(i,i) \times (k-i)+cost(k+1,j) \times (k-i+1)$ （ $cost(i,j)$ 表示 $i \sim j$ 這些人的權(quán)值和， $k$ 為區(qū)間內(nèi)一個數(shù)）。

具體看本題提供的代碼。

例 $2.1.5$ CodeForces 149D Coloring Brackets

數(shù)組要記錄區(qū)間左右端點(diǎn)的染色情況。

如果左右端點(diǎn)是一對匹配的括號，那么推到 $(i+1,j-1)$ ，再分類討論。

否則，推到 $(i,k)$ 和 $(k+1,j)$ ，其中 $k$ 是與 $i$ 匹配的括號。再分類討論。具體的轉(zhuǎn)移方程不是特別難，根據(jù)題意可以自行推導(dǎo)。

提供本題代碼。

$\text{Part}2.2$ 取一端/兩端套路

例 $2.2.1$ POJ 2955 Brackets

這題我是真不知道歸 $2.1$ 還是歸類 $2.2$ ，其實(shí)都有。

它和石子合并大致相同?？梢悦杜e $(i,j)$ 中間點(diǎn) $k$ ，得 $\text{dp}_{i,j}=\max \{ \text{dp}_{i,k}+\text{dp}_{k+1,j}\}$ 。但，要注意，如果左端點(diǎn)與右端點(diǎn)括號匹配，長度可以是抹掉左右端點(diǎn)的值加上 $2$ ，因?yàn)檫@對括號可以用了。特判一下即可。

例 $2.2.2$ Luogu P1005 [NOIP2007 提高組] 矩陣取數(shù)游戲

取一端的經(jīng)典問題。從小區(qū)間推向大區(qū)間。轉(zhuǎn)移方程 $\text{dp}_{i,j}$ 會轉(zhuǎn)移到 $\text{dp}_{i,j-1}$ 或者 $F_{i+1,j}$ 。也可以是大區(qū)間推向小區(qū)間： $\text{dp}_{i-1,j}$ 和 $\text{dp}_{i,j+1}$ 。本題以大區(qū)間推向小區(qū)間來講。

問題如何知道一個數(shù)字取得時候是第幾個取的。如果取的是第 $i-1 \operatorname{or} j+1$ 個，則是區(qū)間外的數(shù)量，即 $m-j+i-1$ 。

注意這題需要做 $n$ 次 $\text{dp}$ ，并且需要高精度/__int128。

例題 $2.2.3$ Luogu P3205 [HNOI2010]合唱隊(duì)

也是取一端的經(jīng)典問題。但是這題要考慮兩種情況，一種是一個區(qū)間內(nèi)最后插入左端點(diǎn)，一個是最后插入右端點(diǎn)。當(dāng)然一個轉(zhuǎn)移為 $(i+1,j)$ ，一個轉(zhuǎn)移為 $(i,j-1)$ 。在轉(zhuǎn)移過去的時候，左/右端點(diǎn)在符合條件的情況下均可以，需要判斷。

例題 $2.2.4$ POJ 3280 Cheapest Palindrome

非常古老的問題了。

如果區(qū)間 $(i,j)$ 的左端點(diǎn)與右端點(diǎn)相同，直接推鍋給 $(i+1,j-1)$ 。

否則分四種情況：

在 $i$ 前插入 $str_j$ ，那么推鍋給 $(i,j-1)$
刪掉 $str_j$ ，推鍋給 $(i,j-1)$
在 $j$ 后面插入 $str_i$ ，那么推鍋給 $(i+1,j)$
刪掉 $str_i$ ，推鍋給 $(i+1,j)$ 。

計(jì)算一下每次加上的權(quán)值，然后就做完了。

例 $2.2.5$ ZhimaOI #520 隊(duì)列（未注冊 zhimaoi.cn 的人請注冊）

恰，很有意思嘛。

首先貪心肯定是不對滴。 $\text{Hack Data}$ ：

4
1 6 1000000 5

我們對于每一個區(qū)間 $(i,j)$ 開兩個數(shù)組，一個記錄 當(dāng)前小明取的情況，一個記錄 當(dāng)前小華取的情況 。值是小明能夠得到的最多的和。然后分類討論：

小明則希望自己能得多的，于是在 $\text{dp}_{i,j-1}+a_j$ 和 $\text{dp}_{i+1,j}+a_i$ 之間取最大值。注意這里的 $\text{dp}$ 是小華取的情況。
小華則希望小明得的少，于是在 $\text{dp}_{i,j-1}$ 與 $\text{dp}_{i+1,j}$ 里面取最小值。注意這里的 $\text{dp}$ 是小明取的情況。

因?yàn)榉中∪A和小明，所以我們要分兩個 $\text{dp}$ 數(shù)組。

$\text{Part}2.3$ 關(guān)路燈套路

例 $2.3.1$ Luogu P1220 關(guān)路燈

分兩種情況：老王在左端點(diǎn)；老王在右端點(diǎn)。轉(zhuǎn)移到的區(qū)間決定于老王在的位置。老王這么做顯然會讓區(qū)間外以及現(xiàn)在要關(guān)的路燈都等相應(yīng)的時間。

設(shè) $F_{i,j,0/1}$ 分別為老王在 $i/j$ 處，關(guān)掉 $(i,j)$ 之間的燈所需最小耗能。轉(zhuǎn)移方程我則以代碼形式表示：

f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+(a[i+1]-a[i])*(sum[i]+sum[n]-sum[j]));
f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+(a[j]-a[i])*(sum[i]+sum[n]-sum[j]));
f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+(a[j]-a[j-1])*(sum[i-1]+sum[n]-sum[j-1]))
f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+(a[j]-a[i])*(sum[i-1]+sum[n]-sum[j-1]));

其中， $sum_k = \sum \limits_{i=1}^k b_i$ ， $b_i$ 則為功率， $a_i$ 為位置。

例 $2.3.2$ ZOJ 3469

和上一題思路一模一樣！Code 不給了。

例 $2.3.3$ Luogu P2858 [USACO06FEB]Treats for the Cows G/S

也是關(guān)路燈類問題。注意：這題的起點(diǎn)可以是任意位置哦！

設(shè) $\text{dp}_{i,j}$ 表示取掉了 $(i,j)$ 之間的零食獲得的最大權(quán)值。注意我們倒推做， $\text{dp}_{i,i}$ 是第 $i$ 個零食最后一個拿，長度為 $2$ 的區(qū)間的 $\text{dp}$ 是這兩個零食最后拿的最大全職。

對于長度為 $len$ 的區(qū)間 $(i,j)$ ，我們可以求得左/右端點(diǎn)是第 $(n-len+1)$ 個取的。這樣就很好計(jì)算了。

$\text{Part}2.4$ “找對象”套路

（相信你現(xiàn)在可以自己推導(dǎo)轉(zhuǎn)移方程了！）

先解釋一下：這類題目與三元組有關(guān)，所以我們可以給端點(diǎn) $(i,j)$ 找一個合適的 $k$ 組成三元組。

例 $2.4.1$ LibreOJ #10149. 「一本通 5.1 例 3」凸多邊形的劃分

對于區(qū)間 $(i,j)$ ，我們找一個點(diǎn) $k$ 與其組成三角形，計(jì)算出結(jié)果，然后講區(qū)間劃分為 $(i,k)$ 與 $(k,j)$ （畫圖試一下）。然后就是合并果子了？！

注意：需要使用 __int128。

例 $2.4.2$ POJ 1651 Multiplication Puzzle

$\text{dp}_{i,j}$ 表示刪掉 $(i+1,j-1)$ 之間的區(qū)間的數(shù)字的最大獲得權(quán)值。我們找到和 $i,j$ 一起刪掉的 $k$ 。

首先要刪掉 $(i+1,k-1)$ ，然后刪掉 $(k+1,j-1)$ （兩個 $\text{dp}$ 值加上），再加上 $a_i\times a_j \times a_k$ ，就是當(dāng)前 $k$ 所得到的權(quán)值，枚舉 $k$ 即可。 $k$ 是中間的切斷點(diǎn)。

例 $2.4.3$ HDU 5115 Dire Wolf

肥腸簡單，和上一題一樣。還是有些代碼細(xì)節(jié)，所以提供本題代碼。

$\text{Part}2.5$ 涂色套路

例 $2.5.1$ Luogu P4170 [CQOI2007]涂色

如果左右端點(diǎn)相同，涂 $i$ 的時候可以順帶涂一下 $j$ ；涂 $j$ 的時候可以順帶涂一下 $i$ 。也就是，一個端點(diǎn)可以忽略。否則，枚舉中轉(zhuǎn)點(diǎn)涂。

例 $2.5.2$ HDU 2476 String painter

先考慮空串變?yōu)? $\text{B}$ 串。對于區(qū)間 $(i,j)$ ，如果有中轉(zhuǎn)點(diǎn) $k$ ，它的字母等于 $j$ ，那么涂 $(k,j-1)$ 的時候可以順帶涂一下 $j$ 。區(qū)間 $(i,k-1)$ 再考慮。

但是在 $\text{A}$ 串的基礎(chǔ)上就麻煩了。對于一個本來就匹配的字母，我們可刷可不刷。具體的操作，我們可以用 $a_i$ 表示前 $i$ 個字母轉(zhuǎn)換的值。如果 $A_i=B_i$ ， $a_i$ 可以是 $a_{i-1}$ ；否則僅僅可以是 $a_k+\text{dp}_{k+1,i}$ 。

例 $2.5.3$ LightOJ 1422 Halloween Costumes

歡迎大家在這里提交。

看著不像涂色，可是它就是涂色！

首先，對于區(qū)間 $(i,j)$ ，我們找到要穿的衣服與 $j$ 相同的 $k$ 。我們先轉(zhuǎn)移到區(qū)間 $(i,k)$ ，這個值先加上。要注意：此時穿著的衣服是第 $k$ 次演出所需衣服，和 $j$ 相同。我們再加上區(qū)間 $(k+1,j-1)$ 。為啥是 $j-1$ ？因?yàn)? $j$ 的衣服已經(jīng)被 $k$ 準(zhǔn)備好了，到時候不斷脫衣服直到 $k$ 露出來。

這篇文章結(jié)束了！這是博客版文檔，所有參考代碼請?jiān)?這里下載，或者登錄洛谷，在云剪切板中查看。

原文地址

PS:

求區(qū)間 DP 好題，本文章會不斷更新！

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

區(qū)間dp總結(jié)+題解

區(qū)間dp總結(jié)+題解

$\text{Part} 0$ 區(qū)間 $\text{dp}$ 是什么

$\text{Part}1$ 區(qū)間 $\text{dp}$ 架構(gòu)

$\text{Part}2$ 神奇的“套路”們

$\text{Part}2.1$ 石子合并類套路

$\text{Part}2.2$ 取一端/兩端套路

$\text{Part}2.3$ 關(guān)路燈套路

$\text{Part}2.4$ “找對象”套路

$\text{Part}2.5$ 涂色套路

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

區(qū)間dp總結(jié)+題解

區(qū)間 是什么

區(qū)間 架構(gòu)

神奇的“套路”們

石子合并類套路

取一端/兩端套路

關(guān)路燈套路

“找對象”套路

涂色套路

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

$\text{Part} 0$ 區(qū)間 $\text{dp}$ 是什么

$\text{Part}1$ 區(qū)間 $\text{dp}$ 架構(gòu)

$\text{Part}2$ 神奇的“套路”們

$\text{Part}2.1$ 石子合并類套路

$\text{Part}2.2$ 取一端/兩端套路

$\text{Part}2.3$ 關(guān)路燈套路

$\text{Part}2.4$ “找對象”套路

$\text{Part}2.5$ 涂色套路