動態規劃

• 前言
• 手把手如何寫動態規劃
• • 最長路徑
  • 網格
• 最長上升子序列問題
• • 求最長上升子序列
  • 最長非嚴格遞增子序列
  • 至少修改多少次能將序列變為上升序列
• 最長公共上升子序列
• 分級問題
• 移動服務
• 傳紙條
• 排序不等式
• 背包問題
• • 前言
  • 01背包問題
  • • 01背包進階
    • 數字組合
• 完全背包
• • • 自然數拆分
    • 陪審團
  • 多重背包
  • • 二進制優化版
    • 單調隊列優化版
    • • 分組背包
  • 區間DP
  • • 環形石子和并

前言

本篇依據y總的方法，采用集合的框架力來力求解釋好dp的原因。
框架的整體是：

手把手如何寫動態規劃

第一點肯定是經驗了，寫了一定量的題目后你才能動態規劃知其所以然。

難點是動態規劃的計算上面難點就是狀態的計算上面了。動態規劃是一種特殊的最短路問題(在拓補圖上的)。從圖論方面考慮狀態的計算，其實就是，不同狀態之間的轉換關系（有向邊的關系）

轉換關系一般有兩大類：

用其所依賴的狀態來更新當前狀態。（80%）

用當前狀態更新依賴它的狀態。
畫圖來說就是
這兩種其實是等價的。

下面以兩個題目來進行說明

最長路徑

題目轉送門

首先我們可以寫出動態規劃的表達式(很大程度考經驗)，dp[i]表示 y以節點i結尾的最長路徑長度。那么我們如何進行更新呢，首先這個點的前一個狀態是什么情況我呢吧不好知道，但是因為由這個點指向的下一個點的情況我們是可以很好的知道的，就是該點的路徑長度+1，（就是上圖第二類的情況），我們可以有當前狀態更新依賴它的狀態。
那么更新的順序是什么呢?結合題目的有向無環圖，那么我們就可以按照拓撲序的順秀來進行更新。

代碼：

#include <iostream> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int N = 2e5 + 10; int n, m, cnt; int h[N], ne[N], e[N], in[N]; int f[N];void add(int u, int v) {e[++cnt] = v, ne[cnt] = h[u], h[u] = cnt; }void tosort() {queue<int>q;for (int i = 1; i <= n; ++i)if (!in[i])q.push(i);while (q.size()) {int u = q.front();q.pop();for (int i = h[u] ; ~i ; i = ne[i]) {int v = e[i];f[v] = max(f[v], f[u] + 1);if (--in[v] == 0)q.push(v);}} }int main() {cin >> n >> m;memset(h, -1, sizeof h);while (m--) {int a, b;cin >> a >> b;add(a, b);in[b]++;}tosort();int res = 0;for (int i = 1 ; i <= n ; ++i)res = max(res, f[i]);cout << res << endl;return 0; }

網格

題目轉送門
上面一題是第二類情況，那么這題就講一下第一類的情況；

首先我們定義的動態規劃的狀態是：dp[i][j] : 表示從(1,1)到(i,j)的路徑數量。
由題意，對于每一個dp[i][j] ，他都是只能從上方或者左方過來的，因此對于每一個dp[i][j]加上它的這兩個方向的路徑數量即可。

代碼：

#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1010, mod = 1e9 + 7 ; int n, m ; char g[N][N]; int f[N][N];int dx[2] = {-1, 0}, dy[2] = {0, -1};int main() {cin >> n >> m;for (int i = 0 ; i < n ; ++i)cin >> g[i];f[0][0] = 1;for (int i = 0 ; i < n ; ++i)for (int j = 0 ; j < m ; ++j) {if (g[i][j] == '#')continue;for (int k = 0 ; k < 2 ; ++k) {int xx = i + dx[k], yy = j + dy[k];if (xx < 0 || xx >= n || yy < 0 || yy >= m)continue;if (g[xx ][yy ] == '.')f[i][j] = (f[i][j] + f[xx][yy]) % mod;}}cout << f[n - 1][m - 1] << endl;return 0; }

最長上升子序列問題

求最長上升子序列

首先我們依據框架來寫一下思路

我們講一下狀態計算中為什么劃分成這樣。f[i]是以A[I]為結尾的所有情況中的最大值。那么我們還是引入last這個概念，對于所有以A[i]結尾的上升序列，由于最后一個都是A[i]那么它們的不同點就是去掉A[I]之后的第一個數，即倒數第二個數。因此我們都去掉A[i]而去枚舉前面滿足，而有含義可以知道這些就是f[1~(i-1]的定義。因此我們就枚舉從1~（i-1）滿足上升的。取最大值。
核心代碼

for(int i = 2 ; i <= n ;++i){for(int j = 1 ; j < i ; ++j )if(a[i] > a[j]) f[i] = max(f[i] , f[j] + 1); }

上面做法很明顯是$O(n^2)$的一個做法。很明顯不能接收。那么我們看如何進行優化呢？重復計算主要是在第二層循環上邊，因為對于每一個i我們都要去前邊找一個最優的前綴序列，不過呢這個題不能想下邊最長公共子序列那樣記錄一個最值，因為在這里后邊的值是可能比前邊小的。因此我們利用貪心的思想，對于同一長度的的LIS我們肯定是希望結尾越小越好。同時這樣維護的序列由于是具有單調性的，因此我們就可以利用二分來優化最終使得算法時間復雜度為：$O(nlongn)$

f[i]的定義是：表示長度為i的LIS結尾元素的最小值。到時候我們的答案就是i的值。

為什么是對的？對于一個LIS序列當遍歷到后邊的時候如果如果我們更新了結尾的值，由貪心思想這是最優的，同時也是可以的，對于如果我們用后邊一個值去修改一個在中間的值，表面上我們不可以這樣因為我們要按順序來取，但是這不會影響最終的結果，因為它不會增加LIS的長度。具體來說，我們想修改的值只是結尾的值，然其最小化，不過如果加上特判只修改結尾值會麻煩，而都修改不會影響最終結果，那何樂而不為之呢？因此我們用這個方法能求出正確的LIS的長度，但里邊存的值不一定是正確的LIS序列。即
但是！！！B[ ] 中的序列并不一定是正確的最長上升子序列

我們二分找的是比a[i]大于或等于的第一個位置，因此我們可以利用lower_bound( )函數：來實現。//返回第一個大于等于val值的位置

核心代碼：

#include <stdio.h> #include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1010, INF = 0x3f3f3f3f; int n, cnt, a[N]; int f[N]; int find(int num) {// 由于加1之后，那么減完 f之后就相當于f以1開始存的下標return lower_bound(f + 1, f + 1 + cnt, num) - f; }int main() {cin >> n;for (int i = 1 ; i <= n ; ++i)cin >> a[i], f[i] = INF;f[1] = a[1], cnt = 1;//從第2個數開始for (int i = 2 ; i <= n ; ++i) {if (a[i] > f[cnt]) // 大于的話直接接在后邊f[++cnt] = a[i];elsef[find(a[i])] = a[i];}cout << cnt << endl;return 0; }

上面做法就有點遍歷dp了，那么我們對dp式子進行分析一下：
我們再來回顧O(n^2)DP的狀態轉移方程：F [ i ] = max { F [ j ] + 1 ，F [ i ] } (1 <= j < i，A[ j ] < A[ i ])
我們在遞推F數組的時候，每次都要把F數組掃一遍求F[ j ]的最大值，時間開銷比較大。我們可以借助數據結構來優化這個過程。那么我們如何優化呢？我們耗時是在一個一個的去與前邊滿足條件的取最大值，那么我們是否可以更快的進行呢？我們就可以采用樹狀數組來進行維護，采用以數值范圍建樹的思想，將LIS長度的最大值記錄下來。那么取最大值這個過程優化了，不過我們利用樹狀數組維護的時候是與該編號前邊的所有取一個最大值，因此對于該編號我們要保證它的值必須要是大的（上升）,因此我們就可以用結構體來存值和編號，對值進行排序，然后從前往后遍歷，那么我們在遍歷的時候就一定是滿足上升的性質。
代碼：

#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; const int maxn =103,INF=0x7f7f7f7f; struct Node{int val,num; }z[maxn]; int T[maxn]; int n; bool cmp(Node a,Node b) {return a.val==b.val?a.num<b.num:a.val<b.val; } void modify(int x,int y)//把val[x]替換為val[x]和y中較大的數 {for(;x<=n;x+=x&(-x)) T[x]=max(T[x],y); } int query(int x)//返回val[1]~val[x]中的最大值 {int res=-INF;for(;x;x-=x&(-x)) res=max(res,T[x]);return res; } int main() {int ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&z[i].val);//如果題目數據沒有說各不相同的話，需要去重。//如果不去重那就是求最長非嚴格單調上升子序列的長度z[i].num=i;//記住val[i]的編號，有點類似于離散化的處理，但沒有去重 }sort(z+1,z+n+1,cmp);//以權值為第一關鍵字從小到大排序 for(int i=1;i<=n;i++)//按權值從小到大枚舉 {int maxx=query(z[i].num);//查詢編號小于等于num[i]的LIS最大長度modify(z[i].num,++maxx);//把長度+1，再去更新前面的LIS長度ans=max(ans,maxx);//更新答案}printf("%d\n",ans);return 0; }

最長非嚴格遞增子序列

這個和上面是幾乎一樣的，由于是非嚴格因此可以等于，因此我們就有可能是等于的情況而已
核心代碼：

for(int i = 2 ; i <= n ;++i){for(int j = 1 ; j < i ; ++j )if(a[i] >= a[j]) f[i] = max(f[i] , f[j] + 1); }

對于第二種方法：

for (int i = 2 ; i <= n ; ++i) {if (a[i] >= f[cnt]) // 大于的話直接接在后邊f[++cnt] = a[i];elsef[find(a[i])] = a[i];}

至少修改多少次能將序列變為上升序列

對于非嚴格遞增序列，我們只需要用序列的總長度減去最長非嚴格遞增序列的長度即可。因為對于不在最長非嚴格遞增序列的數字我們可以將其改為與臨近的數字相等就可以實現了。

對于用嚴格遞增序列，我們先構造出一個數組b, b[i] = a[i] - 1 ，然后求b數組的最長非嚴格遞增子序列的長度，然后用序列總長度減去就得到正確答案了。原因是：對于嚴格遞增序列我們有$a[i]>a[j](i>j)$等價變形為$a[i]?i>=a[j]?j$.對于這個形式我們發現出現了等于號，因此我們就按上述方法構造出一個新的序列。然后用這個新的序列來求。

最長公共上升子序列

題目轉送門


下面就來重點講一下，狀態計算的部分。

首先 ，依據最長公共子序列的思想，因為b[j]一定在這個集合中了那么我們就看a[i]這個元素，由題目有兩個條件，一個是公共，這個是兩個序列之間的關系，一個是上升是序列內部的關系。我們就由公共，分為a[i]不在公共上升子序列中和a[i]在公共上升子序列中兩部分。對于前一個部分，

也就是f[i-1][j]的含義了，我們都是從含義出發來找的。對于后一部分，我們需要借助，lat這個概念，這個是什么意思呢，就最后一個不同的地方，由于后半部分a[i] == b[j]的，那么其不同點就是b[j]上的一個元素是什么了。而b[j]元素前邊有的元素個數可能情況是0~j-1 個。對于0的情況，因為b[j]前邊沒有元素，因此只要我滿足公共就一定是上升了也就是1.（因為就自己一個肯定是上升的）。對于 1 ~ j-1 。我們只要它們的值小于 b[j] 那么就可以進行去max的計算，而在取max的時候，我們的式子是f[i][j] = max(f[i][j] , f[i-1][k] + 1);首先解釋下 i - 1，和為什么我們以有無a[i]來區分，這與我們的遍歷有關，我們外層循環是 a ，如果我們外層循環是 b,那么我們也可以按理將b[i]是否在來進行劃分。然后是f[i-1][k] + 1 。 因為在這個的前提是a[i] = a[j] ，那么就已經滿足了公共的條件了，又有b[k] < b[j] ，那么又滿足了上升的條件那么，f[i-1][k]是這個的前一部分位置，1是a[i] == b[j]這個部分。
我們有以下核心代碼：

for(int i = 1 ; i <= n ; ++i){for(int j = 1 ; j <= n ; ++j){f[i][j] = f[i-1][j];if(a[i] == b[j]){int maxv = 1;for(int k = 1 ; k < j ; ++k)if(b[k] < b[j])maxv = max(maxv , f[i-1][k] + 1);f[i][j] = max(maxv , f[i][j]);}}}int res = 0 ;for(int i = 1 ; i <= n ; ++i)res = max(res , f[n][i]);

這個算法是 $O(n^3)$的一個數量級，我們就想辦法對其進行優化一下。
由于a[i] == b[j],上式代碼就變為了：if(b[k] < a[i])maxv = max(maxv , f[i-1][k] + 1);
那么第三層循環求的就是：

這里邊小于 a[i]的 ， 因為這個是固定的，因為b里邊哪些值小于a[i]都是已經成定居了的。所以這個循環就是求所有的b，b滿足小于a[i]對應的方案數+1的一個最大值。

for(int i = 1 ; i <= n ; ++i){int maxv = 1;for(int j = 1 ; j <= n ; ++j){f[i][j] = f[i-1][j];if(a[i] == b[j])f[i][j] = max(maxv , f[i][j]);if(b[j] < a[i]) maxv = max(maxv,f[i-1][j] + 1 );}}

分級問題

問題轉送們

有了前面的鋪墊我們就直接來說如何進行轉態計算的。首先對于f[i][j]這個狀態它是定的了，就是我第i個位置放的一定是 b[j]這個數了，那么在這個情況下(就是指第i個位置放的一定是 b[j]這個數的所有的可能情況下) ，還是引用last這個概念，我們的第一個不同點應該是上一個位置所放的值，由于要符合非嚴格單調遞增的性質，我們上一個位置能放的值的可能就是 1~j因此我們就對該問題進行了劃分。至于如何求呢我們看下邊

我們發現如果我們用循環來計算，就會有很多的重復計算。我們發現對于后一個j來說除了f[i-1][j+1] 是與j的時候不同的其余都是一樣的。因此我們就可以用一個值來維護這個最小值。

因為這題是有非嚴格遞增和遞減兩種情況，因此我們這兩種情況中取一個最小值即可。那么如果我們先求了遞增，那么只需要，將原數組翻轉一下即可。

#include<stdio.h> #include<iostream> #include<algorithm> #include<cmath>using namespace std;const int N = 2010 , INF = 0X3f3f3f3f3f; int n , a[N] , b[N]; int f[N][N];int dp(){for(int i = 1 ; i <= n ; ++i)b[i] = a[i];sort(b+1,b+1+n);for(int i = 1 ; i <= n ; ++i){int minv = INF;for(int j = 1 ; j <= n ; ++j){minv = min(minv , f[i-1][j]);f[i][j] = minv + abs(b[j] - a[i]);}}int res = INF;for(int i = 1 ; i <= n ;++i)res = min(res , f[n][i]);return res; }int main(){scanf("%d",&n);for(int i = 1 ; i <= n ; ++i)scanf("%d",&a[i]);int res = dp();reverse(a+1 , a+1+n );res = min(res , dp());printf("%d\n",res);return 0; }

移動服務

題目轉送們

解題思路：

首先我們要想如何表示狀態呢？我們可以用完成了第幾個請求作為一個階段，但是光有這個信息還是不夠的，我們就需要附加一些信息。在這個題目中，我們用三個服務員的位置來作為附加的信息。因此我們就有了，f[i][x][y][z]表示的含義是處理第i個請求后三個服務員所在的位置分別為x,y,z。不夠如果我們直接這樣計算時間上直接會TM的。那么我們就需要分析這些附加的信息是否有關聯性呢？由題目含義出發，當我們處理了第i個請求后肯定有一個服務員是在pos[i]這個位置上的，因此后邊的三個信息我們只需要兩個即可。到了這里我們先畫出初步的框架出來。

那么下一個難點就是狀態的計算上面了。動態規劃是一種特殊的最短路問題(在拓補圖上的)。從圖論方面考慮狀態的計算，其實就是，不同狀態之間的轉換關系（有向邊的關系）

轉換關系一般有兩大類：

用其所依賴的狀態來更新當前狀態。（80%）

用當前狀態更新依賴它的狀態。
畫圖來說就是
這兩種其實是等價的。

那么我們會過頭來看一下這個問題，這個狀態的狀態中，對于當前狀態f[i][x][y]它出去的狀態就只有三種，無非是x服務員去，要么是y去，要么是z去。而對于它的入邊就很復雜。因此這一題我們就選用第二種來進行計算。

啟發：

求線性DP的問題，一般先確定“階段”。如果“階段”不足以表示一個狀態，則需要把所需的附加信息也作為狀態的維度。

在確定DP的狀態的時候，要選擇最小的能夠覆蓋整個狀態空間的：維度集合。好比這題我們當然可以用四維的來表示，但是如果能用三維來表示不是更好。

代碼：

#include<stdio.h> #include<iostream> #include<cstring> #include<algorithm> using namespace std;const int N = 1010 , M = 210; int n , m , pos[N]; int w[M][M] , f[N][M][M];int main(){scanf("%d%d",&m,&n);for(int i = 1 ; i <= m ; ++i)for(int j = 1 ; j <= m ; ++j)scanf("%d",&w[i][j]);for(int i = 1 ; i <= n ;++i)scanf("%d",&pos[i]);memset(f , 0x3f , sizeof f);pos[0] = 3 , f[0][1][2] = 0;for(int i = 0 ; i < n ; ++i)for(int x = 1 ; x <= m ; ++x)for(int y = 1 ; y <= m ; ++y){int z = pos[i] , u = pos[i+1] , val = f[i][x][y];if(x == y || x == z || y == z)continue;f[i+1][x][y] = min(f[i+1][x][y] , val + w[z][u]);f[i+1][z][y] = min(f[i+1][z][y] , val + w[x][u]);f[i+1][x][z] = min(f[i+1][x][z] , val +w[y][u]);}int res = 0x3f3f3f3f;for(int x = 1 ; x <= m ; ++x)for(int y = 1 ; y <= m ; ++y){int z = pos[n]; //因為是順序處理請求，因此最后處理的應該是這個請求。if(x == y || y == z || x == z)continue;res = min(res , f[n][x][y]);//}printf("%d\n",res);return 0; }

傳紙條

題目轉送門

解題思路：

這題首先我們回想一下如果是只能走一條路徑的時候我們是如何定于狀態的：f[i][j]:表示走到$(x_i,y_j)$這個路徑的和的最大值。那么我們可以類似的定義為：f[x1][y1][x2[y2]。不過由上面的啟發我們試著想想能不能縮小一下狀態空間呢？我們用了兩個坐標，是為了判斷是否位于同一個格子上即x1 == x2 && y1 == y2，不過這樣分太細了。如果我們記錄的是橫縱坐標的和，那么如果和相同的情況下，只有x相同那么就可以判斷出來了。因此我們最終的狀態表示是：f[k]x1][x2];

那么什么如何由劃分的子區間的含義如何得到表達式呢？

類比，我們得到四個區間的表達式分別為：

• 兩個人同時向右走，最大分值是 f[k - 1, i, j] + score(k, i, j)；
• 第一個人向右走，第二個人向下走，最大分值是 f[k - 1, i, j - 1] + score(k, i, j)；
• 第一個人向下走，第二個人向右走，最大分值是 f[k - 1, i - 1, j] + score(k, i, j)；
• 兩個人同時向下走，最大分值是 f[k - 1, i - 1, j - 1] + score(k, i, j)；

還有一個注意點是x的范圍，我們有$1<=x<=n和1<=k?x<=m$ 得到
$max(1,k?m)<=x<=min(n,k?1)$

對于本題還可以與方格取數有關，相關的證明為這篇博客：博客

代碼：

#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; const int N = 55; int n , m ; int w[N][N], f[N<<1][N][N];int main(){cin>>n>>m;for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= m ; ++j)cin>>w[i][j];for(int k = 2 ; k <= n + m ; ++k)for(int x1 = max(1 , k - m) ; x1 <= min(n , k -1) ; ++x1)for(int x2 = max(1,k-m); x2 <= min(n, k - 1) ; ++x2){int t = w[x1][k-x1] ;if(x1!=x2) t += w[x2][k-x2];for(int a = 0 ; a <= 1 ; ++a)for(int b= 0 ; b <= 1 ; ++b)f[k][x1][x2] = max(f[k][x1][x2] , f[k-1][x1-a][x2-b] + t);}cout<<f[n+m][n][n]<<endl;return 0; }

排序不等式

背包問題

前言

相信大家應該都看過很多講解背包問題的博客或者視頻了。不過這里采用的還是利用上面的框架來進行分析。希望都大家理解上面和運用上面有一個更深的理解。同時在背包問題中我的順序上也是做了一些巧妙的安排。

01背包問題

題目轉送們

如下圖：我們主要來講一下狀態計算這部分。對于f[i][j]我們對比一下這些在這個集合中的所有方案的上一個不同點，對于i來說有的可能是沒有去取第i個物品體積就是j了。因此先分為取和不取兩個劃分。對于取的這部分，那么它們最后一個都是取的i物品是一樣的，那么它們的last不同點就是沒取第i個物品的j的不同。
我們一般是分為變和不變兩個部分，這些方案最后都是取了V[I]這個價值是一樣的，那么不一樣的就是前 i - 1 ，個物品時候的總體積。而我們為了能取到那么總體積就不能小于W[I[

小技巧：

對于一個小數：可以用memset(f , 0xcf , sizeof f); 來初始化。

代碼：

#include<iostream> #include<cstring> using namespace std; const int N = 1010; int n , V; int v[N] , w[N]; int f[N][N]; int main(){memset(f , 0xcf , sizeof f);cin>>n>>V;for(int i = 1 ; i <= n ; ++i)cin>>w[i]>>v[i] ;f[0][0] = 0;for(int i = 1 ; i <= n ; ++i)for(int j = 0 ; j <= V ; ++j){f[i][j] = f[i-1][j];if(j >= w[i])f[i][j] = max(f[i][j] , f[i-1][j-w[i]] + v[i]);}int res = 0;for(int i = 1 ; i <= V ; i++) res = max(res , f[n][i]);cout<<res<<endl;return 0; }

我們觀察發現，每一次求i的時候只與i-1層有關，因此我們可以不用記錄所有的狀態，而采用滾動數組的方法來優化。這里主要講的是另一種優化，我們發現，在每一個階段開始的時候，實際上執行了f[i-1][] 到f[i][]的拷貝,那么我們是不是就可以將狀態空間優化為一維？f[j]表示背包放入總體積為j的物品的最大價值。
先寫出初步的等價變化

不過在第二層循環我們注意，之前我們是f[i-1][j-w[i]] + v[i]表我們在求第i個階段的時候利用的是第i-1階段的信息。現在如果有 V = 2 * w[i] 的話，那么就有 f[V] = max(f[V] , f[w[i]] + v[i]) ， 而 f[w[i]]是我們這個階段剛求出來的這很明顯就不符合了。而這個的解決辦法也很簡單，我們只需要，倒序遍歷即可。

小技巧：如果我們令f數組都是0，而不是只有f[0] = 0 ，那么最后的結果就是f[V]
代碼：

#include<stdio.h> #include<iostream> #include <iostream> #include <algorithm> using namespace std; const int N = 110, M = 1e5 + 10; typedef long long LL; int n, W; int w[N], v[N] ; LL f[M];int main() {cin >> n >> W;for (int i = 1; i <= n ; ++i)cin >> w[i] >> v[i];for (int i = 1; i <= n ; ++i)for (int j = W ; j >= w[i]; --j)f[j] = max(f[j], f[j - w[i]] + v[i]);LL res = 0 ;for (int i = 1 ; i <= W ; ++i)res = max(res, f[i]);cout << res << endl;return 0; }

01背包進階

上面點的01背包的時間復雜度是O（NM）其中N是物品個數，M是背包的容積。因此如果遇到的題目是背包的體積很大，但每一個物品的價值相對小的時候就不能用了。
我們在上面轉態的表示是dp[j]:表示體積為j的物品的最大價值。那么我們就可以修改其中的含義變成：dp[i]：表示價值為i的物品的最小體積。
那么遇到這類情況我們也可以解決了。

代碼：

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 1E5 + 10; typedef long long LL; int n, m ; LL f[N] ; int w[110], v[110];int main() {memset(f, 0x3f, sizeof f );int sum = 0, res = 0;cin >> n >> m;for (int i = 1 ; i <= n ; ++i) {cin >> w[i] >> v[i];sum += v[i];}f[0] = 0;for (int i = 1; i <= n ; ++i)for (int j = sum ; j >= v[i] ; --j) {f[j] = min(f[j], f[j - v[i]] + w[i]);if (f[j] <= m)res = max(j, res);}cout << res << endl;return 0; }

數字組合

題目轉送們

之所以將這兩個放在一起，是因為它們是本質相同的只不過屬性發生了變化的題目。
我們先來寫一些動態規劃的框架

對吧驚人的相識。不過這里計算的是方案的數量。因此我們還是講一下狀態計算的部分。首先是左半部分，那么我們就直接加上其含義的方案數量即可。不過因為對于每一個階段的f[i][j]值都是0，因此我們就可以寫為f[i][j] = f[i-1][j]; 對于右邊的部分，我們只需要把max操作改為加即可。 利用上面提到的小技巧我們直接輸出f[n][m]就是答案了。

代碼：

#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> using namespace std;const int N = 110 , M = 1e4 + 10; int n , m ; int a[N] , f[N][M];int main(){ cin>>n>>m;for(int i = 1 ; i <= n ;++i) cin>>a[i] ;f[0][0] = 1;for(int i = 1 ; i <= n ; ++i){for(int j = 0 ; j <= m ; ++j){ f[i][j] = f[i-1][j];if(j >= a[i])f[i][j] += f[i-1][j-a[i]];}}cout<<f[n][m]<<endl;return 0; }

還是考慮優化版：

#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> using namespace std;const int N = 110 , M = 1e4 + 10; int n , m ; int a[N] , f[M];int main(){ cin>>n>>m;for(int i = 1 ; i <= n ;++i) cin>>a[i] ;f[0] = 1;for(int i = 1 ; i <= n ; ++i)for(int j = m ; j >= a[i] ; --j)f[j] += f[j-a[i]];cout<<f[m]<<endl;return 0; }

完全背包

題目轉送門

完全背包與01背包的區別就是每件物品可以選無限次，只要沒有超過上限的體積。

如果我們直接利用上面的01背包的倒序遍歷的話，我們可以就需要這樣寫。(第i個物品可以選多個) 不過時間復雜度是$O(n^{2}long(n))$是不行的。

講優化01背包的時候，我們為1在計算第i個階段的時候只用i-1個階段的，因此我們從大到小來進行枚舉。而對于完全背包我們只需要將倒序變成正序就可以。

#include<iostream> using namespace std; const int N = 1010; int n , m, w[N] , v[N]; int f[N];int main(){cin>>n>>m;for(int i = 1 ; i <= n ; ++i)cin>>w[i]>>v[i];for(int i = 1 ; i <= n ; ++i)for(int j = w[i] ; j <= m ; ++j )f[j] = max(f[j] , f[j-w[i]] + v[i]);cout<<f[m]<<endl;return 0; }

自然數拆分

題目轉送們

解題思路：

我們將自然數N看成是容量為N的一個背包，那么這題就是有 1 ~N 一共N個物品 ， 每一物品的體積分別從 1 ~N ， 問有這些數字組合為N的所有方案的數量，不過由于可以重復使用，因此該題就是一個完全背包模型了。

同時這個題目是會爆int的，因此我們用unsigned ：$2^{32}?1$.

在c++中有一個性質就是對模上一個負數得到的結果與模上負數的絕對值（正數）其實是一樣的。

陪審團

題目轉送們

解題思路：我們要找的是和之差最小，因為題目兩者之差在$?400???400$那么我們就有一個思路就是以差來劃分，在計算完之后，中差為0開始依次往兩邊找，找到的第一個(因為對稱所以一正一負)就是差最小的，在這兩個之間比較找出最大值，我們通過框架梳理一下思路

還是重點來講一下狀態計算這個部分。結合背包問題的思路，對于f[i][j][k]我們找出最后的不同點出來以此來劃分集合。首先，對于第i個人我們有選與不選兩種劃分。不選由含義出發就是f[i-1][j][k]，如果選的話，

我們將第二部分，的所有情況分為變與不變兩部分，對于不變的就是第i個人，那么前一個部分的含義就是：前i-1個人中，選了j-1個人，差值為 k - (p[i] - d[i]) 而這個就正好是f[i-1][j-1][k - (p[i]-d[i])]。

實現上的難點：由于數組下標不能為負數，因此我們設置一個偏移量 ， 對于0~399 表示負數，401~800表示正數。

可以剪枝的地方，因為我們知道差值只能在-400~400 之間，也就是偏移量之后的0~800.因此如果不在這個范圍內的肯定不是答案。還有一個是我們在第二個方案之前j必須要大于1才可以。

還有一個難點是本題還要輸出一個正確的方案順序：一般這種有兩個解決方法，一個是另開一個數組來存儲狀態的轉移過程，另一個是倒推得到方案，這里我們采用倒推的解決方案。對于這個方法，我們倒推的時候是看當前這個值的一個最值是有dp公式中哪里得到的，另一個關鍵點是，理解倒推時候變量之間的變化。

代碼：

#include<stdio.h> #include<algorithm> #include<iostream> #include<cstring> using namespace std;const int N = 210,M = 810 , base = 400; int n , m ; int ans[N] , p[N] , d[N]; int f[N][21][M]; int main(){int T = 1;while(scanf("%d%d",&n,&m),n&&m){for(int i = 1 ; i <= n; ++i)scanf("%d%d",&p[i],&d[i]);memset(f , -0x3f , sizeof f);f[0][0][base] = 0 ;for(int i = 1 ; i <= n ; ++i)for(int j = 0 ; j <= m; ++j )for(int k = 0 ; k < M ; ++k){f[i][j][k] = f[i-1][j][k];int t = k - (p[i] - d[i]);if(t <0 || t >= M)continue;if(j < 1)continue;f[i][j][k] = max(f[i][j][k] , f[i-1][j-1][t] + p[i] + d[i]);}int v = 0 ;while(f[n][m][base - v] < 0 && f[n][m][base+v] < 0)v++;if(f[n][m][base-v] > f[n][m][base+v]) v = base - v;else v = base + v;int cnt = 0 , i = n , j = m , k = v;while (j){if (f[i][j][k] == f[i - 1][j][k]) i -- ;else{ans[cnt ++ ] = i;k -= (p[i] - d[i]);i --, j -- ;}}int sp = 0 , sd = 0;for(int i = 0 ; i < cnt ; ++i) sp += p[ans[i]] , sd += d[ans[i]];printf("Jury #%d\n",T++);printf("Best jury has value %d for prosecution and value %d for defence:\n",sp,sd);sort(ans, ans + cnt);for(int i = 0 ; i < cnt ; ++i)printf(" %d",ans[i]);puts("\n");}return 0; }

我們對代碼中的倒推過程來進行解釋一下，首先我們明確我們是將選出的m個人的編號給輸出出來，因此我們的循環條件初始條件就是m個人，只有沒有到0也就是還沒有記錄完。 我們看dp中的公式，一個是有可能從f[i-1][j][k]這個狀態中轉移過來的，如果是的話，那么前一個狀態對應的是 i - 1 ， 因此要 i – 。 否則就是由f[i-1][j-1][k-(p[i] - d[i])]得出，因為我們需要先讓 k-(p[i] - d[i]),然后 i-- , j--;

多重背包

題目轉送們

對于多重背包，我們先想一最樸素的做法應該就是將其轉化為01背包問題來解決。在轉化為01背包的問題上我們有兩種想法：

原本的01背包框架應該是這個，一種想法是在選這一步進行改進。對于01背包我們只要選與不選兩種，而對于多重背包在選這個基礎上我們可能選1… c[i]個。那么就有

因此就有：

#include<iostream> using namespace std; const int N = 110; int f[N] , n , m;int main(){cin>>n>>m;for(int i = 1 ; i <= n ; ++i){int w , v , s;cin>>w>>v>>s;for(int j = m ; j >= w ; --j)// k * w <= j ， 即我選了這些后的前一個狀態不可能是小于0的for(int k = 1 ; k <= s && k * w <= j ; k++)f[j] = max(f[j] , f[j- k * w] + k * v); }cout<<f[m]<<endl;return 0; }

還有一種思路是我將這個k * w[i[，分為k次01背包，也就是說將其拆分成一個一個的，然后利用01背包的寫法求解。這兩種是等價的做法。

代碼：

#include<iostream> using namespace std; const int N = 110; int f[N] , n , m;int main(){cin>>n>>m;for(int i = 1 ; i <= n ; ++i){int w , v , s;cin>>w>>v>>s;for(int k = 1 ; k <= s ; ++k)for(int j = m ; j >= w ; --j)f[j] = max(f[j] , f[j- w] + v); }cout<<f[m]<<endl;return 0; }

二進制優化版

首先我們回想一下上面直接拆分為01背包的問題，我們是將其拆為一個一個的物品，因此我們的復雜度很高。這里我們要明確說明一個問題？對于0~n 的數，我們需要使用多少的數才可以將它們表示出來，當然肯定可以，當是最笨的一種方法就是n個1 ，如果一個都不選就表示0，選n個1就表示n。不過這顯然就想我們上面的拆分方式就不可取。這里我們有一個結論：至少需要${\log }_{2}n$這么一個數量的數字。這什么實現呢？好比10： 1 2 4 8 。這顯然是不可以的，因為這就能表示0~15了大于10了。因此我們對于不超過$2^k$的話就直接用剩下就好，就是：1 ， 2 ，4,3。這就可以了。

代碼：

#include<stdio.h> #include<iostream> #include<vector> using namespace std; const int N = 2010; int n , m ,f[N];struct GOOD{int v,w; };int main(){cin>>n>>m;vector<GOOD>goods;for(int i = 1 ; i <= n ; ++i){int v ,w, s;cin>>w>>v>>s;for(int k = 1 ; k <= s ; k *=2){s -= k;goods.push_back({k*v, k *w});}if(s > 0) goods.push_back({s*v,s*w});}for(auto good : goods){for(int j = m ; j >= good.w ; --j)f[j] = max(f[j] , f[j - good.w] + good.v);}cout<<f[m]<<endl;return 0; }

單調隊列優化版

視頻講解轉送門

代碼：

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1010 , M = 20010; int n , m; int f[M] , g[M] ,q[M];int main(){cin>>n>>m;for(int i = 1 ; i <= n ; ++i){memcpy(g , f ,sizeof f);int v , w , s;cin>>v>>w>>s;for(int j = 0 ; j < v ; ++j){int h = 0 ,t = -1;for(int k = j ; k <= m ; k += v){if(h <= t && q[h] < k - s*v )h++;// 【k-s*v ,k-v】//g[q[h]] 當前體積(q[h])下的最大價值，(k - q[h])/v*w 在k下，除了q[h]外還能放的價值if(h <= t)f[k] = max(g[k] , g[q[h]] + (k - q[h])/v*w);//在g中找的，while(h <= t && g[k] >= g[q[t]] + (k - q[t])/v*w)t--;q[++t] = k;}}}cout<<f[m]<<endl;return 0; }

分組背包

題目轉送們
解題思路

這題可以說是01背包模型的拓展吧，與01背包有一點不同的是，我們在選擇一堆物品的時候需要枚舉這一推物品中的所有物品后只選擇一個。我么01的是這一推物品是否選，如果選的話只能在這一推物品中選一個。也可以從另一種角度來想，多重背包是這類題的一個特殊情況，對于多重背包我們可以將一個物品與它的數量看成一堆物品。在這一堆物品中，分別為1個該物品，…，s個該物品。

代碼：

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 110; int n , m ; int w[N] , v[N] ; int f[N];int main(){cin>>n>>m;for(int i = 1 ; i <=n ; ++i){ // 第幾組int s;cin>>s;for(int i = 1 ; i <= s ; ++i)cin>>w[i]>>v[i];for(int j = m ; j >= 1 ; j--) // 體積for(int k = 1 ; k <= s; k++) // 選哪個物品if(j >= w[k])f[j] = max(f[j] , f[j-w[k]] + v[k]);}cout<<f[m]<<endl;return 0; }

區間DP

在區間DP中，一個狀態由若干個比它小且包含與它的區間所代表的狀態轉移過來。區間DP一般是枚舉區間長度，左端點，和劃分區間的位置。（因為右端點可以由區間長度和左端點得到）。

環形石子和并

解題思路：這題關鍵點是，只能合并相鄰的石子，因此我們就能知道如果我們能合并在l和r位置的兩個石子堆，說明這中間的的石子堆已經合并完全了。以下是分析過程：(我們通過分析最大花費來展示）

我們還是來解釋一下狀態計算，對于這個問題我們不好直接計算，那么我們就劃分為子問題，分而治之就簡單了。對于所有和并L和R的所有方案，我們想一下它們的最后的不同點，不同點應該是中間以哪一個位置k作為劃分點將[L,R]區間分為了[L,K],和[K+1,R]兩個部分，因此我們要做的就是枚舉k的位置。同時我們在合并一個區間[L,R]的時候都需要從L到R之間數的和的一個代價，這一步我們就可以利用前綴個來進行優化。

對于環狀我們一般是將其拆分成長度為2n的一個鏈式。只有我們的左右端點就會發生改變，之后我們遍歷一邊[fi,n+i-1]（意思是在第i處將環斷開）取出一個最大值。

代碼：

int n; int a[MAXN]; int g[MAXN][MAXN],f[MAXN][MAXN]; //最大和最小 int sum[MAXN];int main(){scanf("%d",&n);for(int i =1;i<=n;i++){scanf("%d",&a[i]);a[n+i] = a[i]; //構造}for(int i=1;i<=2*n;i++){ //前綴和sum[i] =sum[i-1] + a[i];}memset(g,0x3f,sizeof(g));memset(f,-0x3f,sizeof(f));for(int lena=1;lena<=n;lena++){for(int l=1;l+lena-1 <=n*2;l++){int r = l + lena -1;if(l == r){g[l][r] = f[l][r] = 0;}else {for(int k = l;k < r;k++){g[l][r] = min(g[l][r],g[l][k]+g[k+1][r] + (sum[r] - sum[l-1]));f[l][r] = max(f[l][r],f[l][k]+f[k+1][r] + (sum[r] - sum[l-1]));}}}}int maxn = -INF,minx = INF;for(int i=1;i<=n;i++){ //看n種分割哪種最大和最小minx = min(minx,g[i][i+n-1]);maxn = max(maxn,f[i][i+n-1]);}printf("%d\n%d\n",minx,maxn);return 0; }

總結

以上是生活随笔為你收集整理的动态规划解题思路与总结(三万字)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。