當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

洛谷动态规划一日游 P2577、P1070、P2051

發布時間：2023/12/3 编程问答 27 豆豆

生活随笔收集整理的這篇文章主要介紹了洛谷动态规划一日游 P2577、P1070、P2051 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

記

2018年3月19日

賊頹呢，一天就寫了兩道DP，還都不會寫，這可GG。
動態規劃真的難且有趣，算法題中動態規劃占到了很大的比例，而且動態規劃往往是輔助解決一些其他類型問題的基礎，加深加強對動態規劃問題的認識和訓練非常有必要。

P2577 午餐

題意

題意見題目鏈接

題解

這道題目本質上是一道背包問題，是背包問題的變形,這道題不同的地方在于有兩個背包。
因此，我們設計狀態的時候，兩個背包的狀態都要記錄。

貪心

由于每個隊列的排隊順序不一樣，結果也是不一樣的。而可以證明，當把所有的同學按照其吃飯時間降序排序的話，這樣的排隊順序一定是最優的順序。

樸素

我們最初想到的狀態是這樣的：
dp[i][j][k]表示當前考慮的是前i個人已經被分配，且第一個隊列排隊打飯時間和為i，第二個隊列排隊打飯的時間和為j，最早的集合時間。
那么轉移方程可以寫成
dp[i][j][k]=min(max(dp[i?1][j?a[i]][j],j+b[i]),max(dp[i?1][j][k?a[i]],k+b[i]))
轉移方法：把i分給第1個窗口或者把i分給第2個窗口。

顯然這樣時間、空間復雜度會爆炸。
空間復雜度為O(2005)

優化

因此我們必須優化，進一步挖掘條件以降維。
我們發現j+k=sumb[i]
這樣的話，我們直接可以減少一維，定義
dp[i][j]表示考慮前i個人，第一個窗口的同學總打飯時間為j時候，前i個同學最早集合的時間。
空間復雜度變成了O(2003)
轉移方程:
dp[i][j]=min(max(dp[i?1][j?a[i]],j+b[i]),max(dp[i?1][j],sumb[i]?j+b[i]))

進一步優化

由于我們發現i狀態的轉移只與i-1有關系，因此，我們可以用滾動數組繼續優化掉一維。
時間復雜度O(2002)
總的時間復雜度為O(2003)

細節

注意邊界條件以及轉移成立的條件。

代碼

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef pair<int,int> pii; const int maxn = 205; const int inf = 0x3f3f3f3f; pii ps[maxn]; int dp[2][maxn*maxn],sum[maxn]; int n; int main(){memset(dp,0x3f,sizeof(dp));scanf("%d",&n);for(int i = 0;i < n;++i){int a,b;scanf("%d%d",&a,&b);ps[i+1] = make_pair(-b,a);}sort(ps+1,ps+1+n);dp[0][0] = 0;for(int i = 1;i <= n;++i){memset(dp[i&1],0x3f,sizeof(dp[i&1]));sum[i] = sum[i-1] + ps[i].second;for(int j = 0;j <= sum[i];++j){if(j >= ps[i].second)dp[i&1][j] = min(dp[i&1][j],max(dp[(i-1)&1][j-ps[i].second],j-ps[i].first));if(sum[i]-j >= ps[i].second)dp[i&1][j] = min(dp[i&1][j],max(dp[(i-1)&1][j],sum[i]-j-ps[i].first));}}int mi= inf;for(int j = 0;j <= sum[n];++j){if(dp[n&1][j] < mi){mi = dp[n&1][j];}}cout<<mi<<endl;return 0; }

P1070道路游戲

題意

題目鏈接看題意

題解

這道題本質上就是在下圖斜線上的dp。

Column表示機器人出售站。
Row表示時間軸。
字母相同的斜線上相鄰的兩個表格表示由上一個表格的數字，下一步將取到下面表格的數字。
這樣就相當于我們把整個表格橫著切幾段，然后每一段內部選一條連續的斜線，并把斜線里的數字加起來減去該段斜線第一個站點的費用。把所有的段的值加起來得到一個新的數值，我們要做的就是最大化這個數值。
定義狀態：
opt[i]表示前i行所能收集的最大金幣值。
sum[i][j]表示從第一行的第i站出發，沿著斜線走，一共收集j格的金幣得到的總和。

那么狀態轉移方程就是
i表示行， $j$ 表示機器人購買點所在的斜線編號。
k表示上一次剛好停在哪一行。
$o p t [i] = m a x (o p t [k] + s u m [j] [i] ? s u m [j] [k] ? c o s t [j + k]), 1 < = k < = p$
解釋為什么cost的下標是j+k:

因為j表示的斜線編號，在第k+1行買機器人，實際的購買站點是j+k

這樣做的話，時間復雜度是O(n?m?p)不滿足要求，因此我們必須繼續優化。
看著形式，我就只能想到單調隊列或者是斜率優化了，這道題單調隊列優化顯然是可以的。
我們i,j循環變量不能省略，能省略的就只有k了。我們把i和j與k分離開：
opt[i]=max(sum[j][i]+(opt[k]?sum[j][k]?cost[j+k])),1<=k<=p
分離出來的這部分：
(opt[k]?sum[j][k]?cost[j+k])
就只與k和 $j$ 有關了，因此，我們可以建立n個單調隊列對應 $j$ ，隊列內部對應k。

dp核心代碼

for(int i = 1;i <= m;++i){//i表示時刻for(int j = 1;j <= n;++j){//j表示機器人的購買點所在的斜線編號while(PQS[j].size() && i-PQS[j].getfront().first > p) PQS[j].pop();pii p = PQS[j].getfront();opt[i] = max(opt[i],sum[j][i] + p.second);}for(int j = 1;j <= n;++j){int pre = j+i;while(pre > n) pre -= n;PQS[j].push(i,opt[i] - sum[j][i] - cost[pre]);}}

總的代碼

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 1005; typedef pair<int,int> pii;struct PQ{pii ps[maxn];int front,tail;void push(int idx,int key){while(tail > front && key >= ps[tail-1].second)tail--;ps[tail++] = make_pair(idx,key);}void pop(){if(front < tail) ++front;}int size(){return tail-front;}pii getfront(){return ps[front];} }PQS[maxn];int n,m,p; int val[maxn][maxn]; int sum[maxn][maxn];//1:出發點 2: 步數 int opt[maxn]; int cost[maxn]; const int inf = 1e9; int main(){scanf("%d%d%d",&n,&m,&p);for(int i = 1;i <= n;++i){for(int j = 1;j <= m;++j){scanf("%d",&val[i][j]);}}for(int i = 1;i <= n;++i){scanf("%d",&cost[i]);}for(int i = 1;i <= n;++i){int pre = i-1;for(int j = 1;j <= m;++j){if(++pre == n+1) pre = 1;sum[i][j] = sum[i][j-1]+val[pre][j];//printf("i:%d,j:%d,sum:%d\n",i,j,sum[i][j]);}}for(int i = 1;i <= n;++i)PQS[i].push(0,-cost[i]); for(int i = 1;i <= m;++i)opt[i] = -inf;//dpfor(int i = 1;i <= m;++i){//i表示時刻for(int j = 1;j <= n;++j){//j表示機器人購買點所在的斜線編號while(PQS[j].size() && i-PQS[j].getfront().first > p) PQS[j].pop();pii p = PQS[j].getfront();opt[i] = max(opt[i],sum[j][i] + p.second);}for(int j = 1;j <= n;++j){int pre = j+i;while(pre > n) pre -= n;PQS[j].push(i,opt[i] - sum[j][i] - cost[pre]);}}cout<<opt[m]<<endl;return 0; }

P2051 中國象棋

題意

點擊鏈接查原題目

題解

我好菜啊，這道是原題，暑假集訓的時候做過，而且當時還獨自做出來了，過了半年，自己再做的時候發現竟然不會做了，看了題解的提示才想出來。咋越練越菜呢？？？

這道題目關鍵點在狀態的定義！

我們需要把無用的信息都去除掉，在狀態定義的時候盡量捕捉最本質、最關鍵的信息。
例如本題，按行考慮，在考慮到第i行的時候，我們關注點在前i行中，形成的0炮列有幾個，1個炮的列有幾個，2個跑的列有幾個，這樣。
而我們不需要知道具體的前i行的棋子排列。

狀態定義就出來了：
$d p [i] [j] [k]$ 表示前i行，構成有j個1炮列、k個2炮列可行的方案數。
這樣的話，轉移方程也很容易得到，就是乘法原理。

注意分類的時候這樣分：
第i行不加棋子的轉移、加1個棋子的轉移、加2個棋子的轉移。

加1個棋子的轉移又可以分為：把這個棋子加到0炮列，把這個棋子加到1炮列。

加2個棋子的轉移又可以分為：全都加到0炮列、全都加到1炮列、0炮列1炮列分別加一個。

按照這樣分類轉移，轉移方程很好寫。

代碼

#include <iostream> #include <cstdio> using namespace std; typedef long long ll; ll n,m; const int maxn = 106; const ll mod = 9999973; ll dp[maxn][maxn][maxn]; int main(){cin>>n>>m;dp[1][0][0] = 1;dp[1][1][0] = m;dp[1][2][0] = m*(m-1)/2;for(int i = 2;i <= n;++i){for(int j = 0;j <= m;++j){for(int k = 0;k+j <= m;++k){//0dp[i][j][k] = dp[i-1][j][k];//1if(j >= 1){ll p = m - k - (j-1);dp[i][j][k] += dp[i-1][j-1][k]*p%mod;dp[i][j][k] %= mod;}if(k-1 >= 0){dp[i][j][k] += dp[i-1][j+1][k-1]*(j+1)%mod;dp[i][j][k] %= mod;}//2if(j >= 2){ll p = (m-k-j+2);p = p*(p-1)/2%mod;dp[i][j][k] += dp[i-1][j-2][k]*p%mod;dp[i][j][k] %= mod;}if(k >= 2){ll p = (j+2)*(j+1)/2%mod;dp[i][j][k] += dp[i-1][j+2][k-2]*p%mod;dp[i][j][k] %= mod;}if(k >= 1){ll p = m - j - (k-1);dp[i][j][k] += dp[i-1][j][k-1]*j*p%mod;dp[i][j][k] %= mod;}//dp[i][j][k] += }}}ll ans = 0;for(int i = 0;i <= m;++i){for(int j = 0;j+i <= m;++j){ans = (ans + dp[n][i][j])%mod;}}cout<<ans<<endl; }

總結

以上是生活随笔為你收集整理的洛谷动态规划一日游 P2577、P1070、P2051的全部內容，希望文章能夠幫你解決所遇到的問題。

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