題意：有一道線性籬笆由N個(gè)連續(xù)的木板組成。有K個(gè)工人，你要叫他們給木板涂色。每個(gè)工人有3個(gè)參數(shù)：L 表示 這個(gè)工人可以涂的最大木板數(shù)目，S表示這個(gè)工人站在哪一塊木板，P表示這個(gè)工人每涂一個(gè)木板可以得到的錢。要注意的是，工人i可以選擇不涂任何木板，否則，他的涂色區(qū)域必須是連續(xù)的一段，并且S[i]必須包含在內(nèi)。 最后還有，每塊木板只能被涂一次。?

解題思路：這是一道單調(diào)隊(duì)列優(yōu)化dp的問(wèn)題，首先狀態(tài)dp[i][j]表示第i個(gè)工人刷的最后一塊木板為j，注意：木板可刷可不刷，工人也可以不刷任何墻。之前我忘記了，所以狀態(tài)方程只寫對(duì)了一半：dp[i][j] = max(dp[i][j],dp[i-1][k] + (j-k)*p[i])，這里還有，dp[i][j] = max(dp[i][j],dp[i-1][j],dp[i][j-1]) //第i個(gè)人不刷，第j面墻不刷

這里的關(guān)鍵是如何優(yōu)化方程，注意到dp[i][j]=max(dp[i-1][k]-k*p[i])+j*p[i]，可以直接維護(hù)dp[i-1][k]-k*p[i]的最大值即可，這里用到的就是單調(diào)隊(duì)列。

參考博客：http://www.cnblogs.com/proverbs/archive/2012/10/04/2711751.html

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;struct Node {int l,p,s; }worker[105]; int n,k,dp[105][16005],q[16005]; int head,tail,l[105],r[105];bool cmp(Node a,Node b) {return a.s < b.s; }int main() {while(scanf("%d%d",&n,&k)!=EOF){for(int i = 1; i <= k; i++)scanf("%d%d%d",&worker[i].l,&worker[i].p,&worker[i].s); sort(worker+1,worker+1+k,cmp);for(int i = 1; i <= k; i++){l[i] = max(worker[i].s - worker[i].l,0);r[i] = min(worker[i].s + worker[i].l - 1,n);}memset(dp,0,sizeof(dp));for(int i = 1; i <= k; i++){for(int j = 0; j <= n; j++) dp[i][j] = dp[i-1][j]; //第i名工匠不刷任何墻head = tail = 0;for(int j = l[i]; j < worker[i].s; j++) //將dp[i-1]層的最優(yōu)狀態(tài)存入單調(diào)隊(duì)列 {int tmp = dp[i-1][j] - j * worker[i].p;while(head < tail && dp[i-1][q[tail-1]] - q[tail-1]*worker[i].p <= tmp) tail--;q[tail++] = j;}for(int j = worker[i].s; j <= r[i]; j++){while(head < tail && j - q[head] > worker[i].l) head++; //彈出不在范圍內(nèi)的元素dp[i][j] = max(dp[i][j-1],dp[i-1][j]);dp[i][j] = max(dp[i][j],dp[i-1][q[head]] + (j - q[head]) * worker[i].p);}for(int j = r[i] + 1; j <= n; j++)dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}printf("%d\n",dp[k][n]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj 1821(单调队列优化dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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