題意：有m個階段，每個階段都有n個龍珠，當在某一階段選擇一個龍珠，該階段其他龍珠都會消失。給出兩個m*n的矩陣，第一個矩陣表示消滅第i個階段第j個龍珠的位置，第二個矩陣表示取第i個階段第j個龍珠消耗的能量，同時當第x個位置到第個位置需要消耗 | y - x|的能量。問最后每個階段取走一個龍珠最小的能量消耗。

解題思路：dp[i][j]表示第i個階段選擇第j個龍珠的最小耗能。

轉移方程：dp[i][j] = min{dp[i-1][k] + abs(loc[i][j] - loc[i-1][k]) + cost[i][j]}，這里需要枚舉的是i，j，k所以時間復雜度O(M*N*N)，這題數據好像卡得不是很緊，所以運氣好點是可以AC的。不過不是正解。

這里可以利用單調隊列。因為dp[i][j]=min{dp[i-1][k] - loc[i-1][k] + loc[i][j] + cost[i][j]} ?（loc[i][j] > loc[i-1][k]）,所以可以只需要維護dp[i-1][k] - loc[i-1][k]即可。由于有絕對值，所以我這里用了兩個單調隊列，一個維護dp[i-1][k] - loc[i-1][k]，另一個維護dp[i-1][k] + loc[i-1][k]，但不知道什么原因WA了。。。

先放在這里，等以后有思路了再改吧。。也希望路過我博客的哪位大神指點指點。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int maxn = 1005; const int inf = 0x3f3f3f3f; struct Node {int pos,cost; }mat[55][maxn]; int n,m,x; int dp[55][maxn],q1[maxn],q2[maxn],h1,h2,t1,t2;bool cmp(Node a,Node b) {return a.pos < b.pos; }int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&m,&n,&x);memset(dp,inf,sizeof(dp));for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)scanf("%d",&mat[i][j].pos);for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++)scanf("%d",&mat[i][j].cost);sort(mat[i]+1,mat[i]+1+n,cmp);<span style="white-space:pre"> </span>//排序為了保證進入隊列時，位置是遞增的}for(int i = 1; i <= n; i++)dp[1][i] = abs(x - mat[1][i].pos) + mat[1][i].cost;for(int i = 2; i <= m; i++){h1 = h2 = t1 = t2 = 0;for(int j = 1; j <= n; j++) //將dp[i-1]層的最優狀態放入單調隊列{while(h1 < t1 && dp[i-1][j] - mat[i-1][j].pos <= dp[i-1][q1[t1-1]] - mat[i-1][q1[t1-1]].pos) t1--;q1[t1++] = j;while(h2 < t2 && dp[i-1][j] + mat[i-1][j].pos <= dp[i-1][q2[t2-1]] + mat[i-1][q2[t2-1]].pos) t2--;q2[t2++] = j;}for(int j = 1; j <= n; j++){while(h1 < t1 && mat[i][j].pos < mat[i-1][q1[h1]].pos) h1++;dp[i][j] = dp[i-1][q1[h1]] + mat[i][j].pos + mat[i][j].cost;while(h2 < t2 && mat[i][j].pos >= mat[i-1][q2[h2]].pos) h2++;dp[i][j] = min(dp[i][j],dp[i-1][q2[h2]] - mat[i][j].pos + mat[i][j].cost);}}int ans = inf;for(int i = 1; i <= n; i++)ans = min(ans,dp[m][i]);printf("%d\n",ans);}return 0; }

PS: 仔細想了想，確實自己的單調隊列有問題，因為我是先把所有的dp[i-1]層的送入隊列，就會出現問題，在我后面的循環枚舉dp[i]層的時候一些有效位置可能不在隊列里。所以參考了別人的代碼，還是要先枚舉dp[i][j]中的j，保證我先選擇第j個位置，由于已經是有序的了，所以就直接找不大于mat[i][j].pos位置的最小值即可，同理，由于有絕對值，所以還要反著循環一次。

詳細的過程看代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int maxn = 1005; const int inf = 0x3f3f3f3f; struct Node {int pos,cost; }mat[55][maxn]; int n,m,x; int dp[55][maxn],q1[maxn],q2[maxn],h1,h2,t1,t2;bool cmp(Node a,Node b) {return a.pos < b.pos; }int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&m,&n,&x);memset(dp,inf,sizeof(dp));for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)scanf("%d",&mat[i][j].pos);for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++)scanf("%d",&mat[i][j].cost);sort(mat[i]+1,mat[i]+1+n,cmp);}for(int i = 1; i <= n; i++)dp[1][i] = abs(x - mat[1][i].pos) + mat[1][i].cost;for(int i = 2; i <= m; i++){int k = 1, Min = inf;for(int j = 1; j <= n; j++){while(k <= n && mat[i][j].pos >= mat[i-1][k].pos){Min = min(Min,dp[i-1][k] - mat[i-1][k].pos);k++;}dp[i][j] = Min + mat[i][j].pos + mat[i][j].cost;}k = n, Min = inf;for(int j = n; j >= 1; j--){while(k >= 1 && mat[i][j].pos <= mat[i-1][k].pos){Min = min(Min,dp[i-1][k] + mat[i-1][k].pos);k--;}dp[i][j] = min(dp[i][j],Min - mat[i][j].pos + mat[i][j].cost);}}int ans = inf;for(int i = 1; i <= n; i++)ans = min(ans,dp[m][i]);printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 4362(单调队列优化dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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