區(qū)間dp專題

基本思想

區(qū)間dp一類的問題往往子問題具有很明顯的區(qū)間性質(zhì),也就是說我們可以通過將子問題定義為整個區(qū)間的一個子區(qū)間.因為一個大區(qū)間可以切分成兩段相鄰的子區(qū)間.從這點出發(fā),我們便可以找到遞推關(guān)系.

1.紙牌游戲

蜘蛛牌游戲規(guī)則是這樣的：只能將牌拖到比它大一的牌上面（$A$最小，$K$最大），如果拖動的牌上有按順序排好的牌時，那么這些牌也跟著一起移動，游戲的目的是將所有的牌按同一花色從小到大排好。為了簡單起見，我們的游戲只有同一花色的牌，但是這樣XCX又覺得太簡單了，于是他把牌數(shù)增加到了$n(1<=n<=100)$，牌隨機的在一行上展開，編號從1到$n$，把第$i$號上的牌移到第j號牌上，移動距離為$abs(i?j)$，現(xiàn)在你要做的是求出完成游戲的最小移動距離。

題解

采用區(qū)間動態(tài)規(guī)劃的方式，但是直接進行區(qū)間DP是沒有任何意義的, 所以實際上我們需要另尋狀態(tài)的定義方式.

我們需要對數(shù)列進行變化一下，我們進行dp的區(qū)間$[a,b]$定義為高度為$a$到高度為$b$的紙牌疊加到一起，所需要的最少距離和。

在一開始，我們定義數(shù)組$arr[x]$中存儲的是高度為$x$的紙牌所在的位置。那么狀態(tài)轉(zhuǎn)移就可以寫成：$dp[a][b]=dp[a][j]+dp[j+1][b]+abs(arr[b]?arr[j])$

這樣的話,問題就迎刃而解了,所以說如何去定義問題是$dp$問題的一大難點和關(guān)鍵點.

代碼

#include<bits/stdc++.h> using namespace std;int a[105],n; int dp[105][105];int main() {int T;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);a[x]=i;}for(int k=2;k<=n;k++){for(int i=1;i<=n-k+1;i++){int l=i,r=i+k-1;dp[l][r]=1e9+7;for(int j=l;j<=r-1;j++)dp[l][r]=min(dp[l][r],dp[l][j]+dp[j+1][r]+abs(a[r]-a[j]));}}printf("%d\n",dp[1][n]);}return 0; }

---

2.Multiplication Puzzle POJ - 1651

在一個序列中，拿走一個數(shù)字，那么得分就是這個數(shù)字以及它相鄰的兩個數(shù)字，這三個數(shù)字的乘積, 求最小得分。

題解

這道題乍一看感覺是區(qū)間DP，但是需要逆向思考的技巧。

記$dp[i][k]$表示以$i$開頭的，長度$k$的區(qū)間。

我們考慮一個區(qū)間的時候，記錄區(qū)間的兩個端點分別為$l,r$。

這個區(qū)間兩側(cè)的端點是不能被拿走的，那么我們考慮最后一個被拿走的數(shù)字$k$，它的得分一定是區(qū)間端點的兩個數(shù)和它的乘積($a[l]?a[k]?a[r]$)。

然后我們考慮區(qū)間$[l,k]$之間的情況，這個區(qū)間被拿的只剩下區(qū)間兩個端點了，所以可以直接用子結(jié)構(gòu)$dp[l][k?l+1]$。

同理區(qū)間$p[k,r]$也被拿的只剩下區(qū)間的兩個端點了，直接用子結(jié)構(gòu)$dp[k][r?l?k+1]$

這樣的話遞推式就非常的清晰了。

$dp[i][k]=min(dp[i][k],dp[i][j+1]+dp[i+j][k?j]+a[i]?a[i+j]?a[i+k?1])$

代碼

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int MAX = 106; int dp[MAX][MAX]; int a[MAX]; int n; int main(){scanf("%d",&n);for(int i = 0;i < n;i++){cin>>a[i];}for(int k = 3;k <= n;k++){for(int i = 0 ;i + k <= n;i++){dp[i][k] = 1e9;for(int j = 1;j < k-1;j++){dp[i][k] = min(dp[i][k],dp[i][j+1] + dp[i+j][k-j] + a[i]*a[i+j]*a[i+k-1]);}}}cout<<dp[0][n]<<endl; }

---

3.括號匹配問題 Brackets POJ - 2955

給定一個括號序列,求最長的合法括號表達式子序列.

題解

再明顯不過的區(qū)間DP的題目了，要求求出給出符號式中最大匹配的括號數(shù)。
考慮區(qū)間$[l,r]$，如果$str[l]$與$str[r]$匹配了，那么轉(zhuǎn)移方程為:

$dp[l][r]=max(dp[l][r],dp[l+1][r?1]+2)$

還有一種情況就是考慮將區(qū)間分成2部分

$dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r])$

然后就成了，沒錯就這么簡單

代碼

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int MAX = 105; char str[MAX]; int dp[MAX][MAX]; int mp[128]; int main(){mp['('] = ')';mp['['] = ']';while(gets(str)){memset(dp,0,sizeof(dp));if(str[0] == 'e'){break;}int n = strlen(str);for(int k = 2;k <= n;k++){for(int i = 0;i + k <= n;i++){//左閉右開 for(int j = i + 1;j < i + k;j++){dp[i][i+k] = max(dp[i][i + k],dp[i][j] + dp[j][i+k]);if(mp[str[i]] == str[i+k-1])dp[i][i+k] = max(dp[i][i+k],dp[i+1][i+k-1]+2);}} }printf("%d\n",dp[0][n]);}return 0; }

---

4.You Are the One HDU - 4283

題目大意就是說給定一個有序序列和一個棧，對于隊伍前頭的一個人，有兩個操作，一個是直接邁向舞臺，另一個操作就是邁入棧中。在一個時間下，邁向舞臺的人可以是原始隊伍里的人，也可以是棧里面的人。舉例來說，假定隊伍此時為 隊首=>4 5<=隊尾，棧此時為 棧頂=>3 2 1 <=棧底,那么下一個時刻可能是4進入棧中，或者4進入舞臺，或者3從棧中去向舞臺。

有$n$個人參加非誠勿擾，每個人都有$n_i$的屌絲值，如果前面有$k$個人比他早，他就會有$(k?1)?(n_i)$的不開心值，你可以讓一些人進入一個小黑屋，來改變上場順序，但是小黑屋是類似棧，先入后出。求最小不開心值.

題解

我們考慮如下事實：

考慮區(qū)間$[l,r]$，區(qū)間長度$k=r?l+1$。

如果區(qū)間的第一個元素可能是第$1$ 一直到第 $k$個進入舞臺的，假設(shè)第一個元素是第$p$個進入舞臺的$1<=p<=k$，那么我們知道第一個元素一定要先入棧，區(qū)間$[l+1,l+k?1]$中的元素一定會先第一個元素而進入舞臺，這樣的話，就轉(zhuǎn)化到了子結(jié)構(gòu)$dp[l+1][l+k?1]$中去了。

同時$[l+k,r]$中的元素一定后于第一個元素而進入舞臺。他們共同要等待的耗費為$p?sum[l+k,r]$，另外還有一部分耗費為$dp[l+k][r]$

綜上所述，得到轉(zhuǎn)移方程

$dp[l][r]=min(dp[l][r],dp[l+1][l+k?1]+(k?1)?a[l+p?1]+p?sum[l+k,r]+dp[l+k][r])$

注意：代碼中用的區(qū)間方式為左閉右開。

代碼

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int MAX = 106; char strA[MAX]; char strB[MAX]; int dp[MAX][MAX]; int ans[MAX]; int n; int main(){while(scanf("%s %s",strA,strB) != EOF){memset(dp,0,sizeof(dp));memset(ans,0,sizeof(ans));n = strlen(strA);for(int i = 0;i < n;i++) dp[i][i+1] = 1;for(int len = 2;len <= n;len++){for(int i = 0;i + len <= n;i++){dp[i][i+len] = dp[i+1][i+len] + (strB[i] == strB[i+len-1]?0:1);for(int j = i+1;j < i+len;j++){dp[i][i+len] = min(dp[i][i+len],dp[i][j]+dp[j][i+len]);} }}ans[0] = strA[0] == strB[0] ? 0:1;for(int i = 1;i < n;i++){ans[i] = dp[0][i+1];if(strB[i] == strA[i])ans[i] = min(ans[i],ans[i-1]);for(int j = 0;j < i;j++){ans[i] = min(ans[i],ans[j] + dp[j+1][i+1]);}}cout<<ans[n-1]<<endl;}return 0; }

---

5.Coloring Brackets CodeForces - 149D

題目大意：

給定合法的括號序列，讓你給括弧上色，并且上色時一定要滿足3個要求：
（1）每個括號要么被上紅色，要么被上藍色，要么不上色。
（2）一對匹配的左右括弧，有且只有其中的一個可以被上色。
（3）相鄰的括弧不能被涂上相同的顏色。

題解

首先我們要進行預(yù)處理，求出每個括號的唯一配對的括號，即尋找他們一一對應(yīng)的關(guān)系，這個預(yù)處理很簡單，用棧操作一下就可以了

gets(str);stack<int> stk;int len = strlen(str);for(int i = 0;i < len;i++){if(str[i] == '('){stk.push(i);}else{int p = stk.top();stk.pop();mp[p] = i;mp[i] = p;}}

下面我們考慮的區(qū)間，全部都是配對合法的區(qū)間！

用一個四維數(shù)組dp[l][r][i][j]表示區(qū)間[l,r]且l處被涂上i色，r處被涂上j色。（規(guī)定無色為0，紅色為1，藍色為2）

那么我們可以得到下面的狀態(tài)轉(zhuǎn)移方程：

（1）當區(qū)間長度只有2時候（兩個括弧一定是配對的，因為我們考慮的所有區(qū)間都是配對合法的區(qū)間），上色方案是非常好確定的。

$dp[l][r][0][1]=1;$
$dp[l][r][0][2]=1;$
$dp[l][r][1][0]=1;$
$dp[l][r][2][0]=1;$

（2）當區(qū)間的左右括弧是配對的時候（判斷左右括弧是否匹配，用到了預(yù)處理得到的結(jié)果）。則有如下轉(zhuǎn)移方法：

if(j != 1) dp[l][r][0][1] = (dp[l][r][0][1] + dp[l+1][r-1][i][j])%MOD; if(j != 2) dp[l][r][0][2] = (dp[l][r][0][2] + dp[l+1][r-1][i][j])%MOD; if(i != 1) dp[l][r][1][0] = (dp[l][r][1][0] + dp[l+1][r-1][i][j])%MOD; if(i != 2) dp[l][r][2][0] = (dp[l][r][2][0] + dp[l+1][r-1][i][j])%MOD;

（3）當區(qū)間非左右配對時，把區(qū)間劃分為左右兩個各自合法 的區(qū)間，轉(zhuǎn)移方程是。

$dp[l][r][i][j]=(dp[l][r][i][j]+dp[l][k][i][p]?dp[k+1][r][q][j]\%MOD)\%MOD;$

這里注意$k$代表的是與l配對的括號，那么$k+1$就是與$r$配對的括號了。（這就是預(yù)處理的作用！）

而在動態(tài)規(guī)劃的實現(xiàn)過程中，我們發(fā)現(xiàn)并非所有的區(qū)間都是合法的，只有少部分的區(qū)間是合法的，因此我們用自頂向下的記憶化dp的方法，這樣可以簡化代碼的實現(xiàn)。

代碼

#include <iostream> #include <cstdio> #include <cstring> #include <stack> #include <algorithm> #define int long long using namespace std; const int MAX = 705; const int MOD = 1e9 + 7; int used[MAX][MAX]; int mp[MAX]; char str[MAX]; int dp[MAX][MAX][3][3]; void dfs(int l,int r){if(used[l][r]) return ;used[l][r] = 1;if(l + 1 == r){dp[l][r][0][1] = 1;dp[l][r][0][2] = 1;dp[l][r][1][0] = 1;dp[l][r][2][0] = 1;return ;}if(mp[l] == r){//配對的情況 dfs(l+1,r-1);for(int i = 0;i < 3;i++){for(int j = 0;j < 3;j++){if(j != 1)dp[l][r][0][1] = (dp[l][r][0][1] + dp[l+1][r-1][i][j])%MOD;if(j != 2)dp[l][r][0][2] = (dp[l][r][0][2] + dp[l+1][r-1][i][j])%MOD;if(i != 1)dp[l][r][1][0] = (dp[l][r][1][0] + dp[l+1][r-1][i][j])%MOD; if(i != 2)dp[l][r][2][0] = (dp[l][r][2][0] + dp[l+1][r-1][i][j])%MOD; }}}else{int k = mp[l];dfs(l,k);dfs(k+1,r);for(int i = 0;i < 3;i++){for(int j = 0;j < 3;j++){for(int p = 0;p < 3;p++){for(int q = 0;q < 3;q++){if(p + q == 0 || p != q ){dp[l][r][i][j] = (dp[l][r][i][j] + dp[l][k][i][p] * dp[k+1][r][q][j]%MOD)%MOD;}}} }} } } main(){gets(str);stack<int> stk;int len = strlen(str);for(int i = 0;i < len;i++){if(str[i] == '('){stk.push(i);}else{int p = stk.top();stk.pop();mp[p] = i;mp[i] = p;}}dfs(0,len-1);int ans = 0;for(int i = 0;i < 3;i++){for(int j = 0;j < 3;j++){ans = (ans + dp[0][len-1][i][j])%MOD;}}cout<<ans<<endl;return 0; }

---

總結(jié)

以上是生活随笔為你收集整理的区间dp专题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。