学习单调队列小结
因為一直在聽身邊的人說什么單調隊列/斜率優化dp/背包，(ps:我也不清楚這樣稱呼對不對，因為我真心是沒見過這些東西)我都覺得那是神一樣的東西。終于抽出時間學了一下。
昨天在朋友一本書里面看到一句話，這里先跟大家分享一下：
沒有人會帶你，人要是沒有學會自立，那么將一無所能;如果過于自立，那也將一無所立.? -----柯林斯
想想自己自學了這么長時間，卻是內心的真實寫照。
一直覺得自己特別失敗，這么長時間了還是一無所成，沒拿什么牌，沒學過多么高深的東西，現在已是遲暮之年的猥瑣學子，不曉得前途在何方。而且隊伍還殘了。。。?????????????????????????????????????????????????? ------------------------------2013.3.15 更
我終于刷完了杭電上面單調隊列的題，其中有有一些簡單的單調隊列題目還有一些背包，動歸的優化，下面的內容我都一一為大家奉上：（ps：我的刷題順序是通過百度“hdu 單調隊列”，不是由易到難）
http://acm.hdu.edu.cn/showproblem.php?pid=3415
題意：給定一個長度為n的環形序列，讓你從中找出一個k長的子序列，使得這段序列的和是所有k長子序列中和最大的那個，輸出和，并輸出得到這個和時的起始位置跟終止位置。
思路：因為還要記錄起始位置跟終止位置，所以很顯然隊列結點還需要記錄下標。我們用一個單調減隊列來維護到當前下標時，前面sum的最小值，當然還需要head++使得長度控制在k的范圍內。循環判斷更新最大值，并記錄相應下標就可以了。
View Code #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <queue> #include <map>using namespace std;const int maxn=100000+5;int a[maxn],sum[maxn<<1],head,tail,n,k,st,ed,ans; struct node {int val;int tag;node(int v=0,int t=0):val(v),tag(t){} }q[maxn<<1];void data_in() {memset(sum,0,sizeof(sum));memset(a,0,sizeof(a));for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}for(int i=n+1;i<=n+k;i++)sum[i]=sum[i-1]+a[i-n]; }int main() {int t;scanf("%d",&t);while(t--){scanf("%d %d",&n,&k);data_in();head=1;tail=1;q[tail]=node(0,1);st=ed=1;ans=sum[1];for(int i=2;i<=n+k;i++){while(head<=tail&&q[tail].val>sum[i-1]) tail--;q[++tail]=node(sum[i-1],i);while(head<=tail&&q[head].tag<=i-k) head++;int tmp=sum[i]-q[head].val;if(tmp>ans){ans=tmp;st=q[head].tag;ed=i;}}if(st>n) st-=n;if(ed>n) ed-=n;printf("%d %d %d\n",ans,st,ed);}return 0; }http://acm.hdu.edu.cn/showproblem.php?pid=3474
題意：可以抽象成給一個只由1和-1組成的循環序列，讓你求以每個點為起點且長度<=串長的子串的最小值。
思路：貼一個好題解:http://blog.csdn.net/xymscau/article/details/6677427
http://acm.hdu.edu.cn/showproblem.php?pid=3530
題意：在一個序列中找一個最長的子序列，使之滿足其最大值跟最小值之差val，m<=val<=k，輸出該子序列的長度。
思路：顯然維護一個單調增隊列跟單調減隊列，如果隊首元素之差滿足條件的時候就更新，不滿足的時候相應指針移動，并用中間變量start記錄一下該序列的起始位置，更新長度即可。
代碼：
View Code #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <queue> #include <vector> #include <map>using namespace std;const int maxn=100000+5;int n,m,k,head1,head2,tail1,tail2,start;struct node {int val;int tag;node(int v=0,int t=0):val(v),tag(t){} }q[2][maxn];int main() {int ans;while(~scanf("%d %d %d",&n,&m,&k)){node tmp;head1=head2=start=1,tail1=tail2=ans=0;for(int i=1;i<=n;i++){scanf("%d",&tmp.val);tmp.tag=i;while(head1<=tail1&&q[0][tail1].val<tmp.val) tail1--;//最大q[0][++tail1]=node(tmp);while(head2<=tail2&&q[1][tail2].val>tmp.val) tail2--;//最小q[1][++tail2]=node(tmp);while(q[0][head1].val-q[1][head2].val>k){start=min(q[0][head1].tag,q[1][head2].tag);start==q[0][head1].tag?head1++:head2++;start++;}if(q[0][head1].val-q[1][head2].val>=m&&q[0][head1].val-q[1][head2].val<=k)ans=max(ans,i-start+1);}printf("%d\n",ans);}return 0; }單調隊列優化：
http://acm.hdu.edu.cn/showproblem.php?pid=1171
又把這個題用單調隊列做了一遍，代碼：
View Code #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio>using namespace std;const int maxn=55;int n,sum,val[maxn],num[maxn]; struct Node {int tag;int val;Node(int t=0,int v=0):tag(t),val(v){}; }que[250005];void init() {sum=0;for(int i=1;i<=n;i++){scanf("%d %d",&val[i],&num[i]);sum+=val[i]*num[i];} }inline int max(int a,int b) {return a<b?b:a; }inline int min(int a,int b) {return a<b?a:b; }int dp[250005]; void DP() {memset(dp,0,sizeof(dp));int sum1=sum/2;for(int i=1;i<=n;i++){num[i]=min(num[i],sum1/val[i]);for(int j=0;j<val[i];j++){int head,tail;head=1,tail=0;for(int k=0;k<=(sum1-j)/val[i];k++){int y=dp[k*val[i]+j]-k*val[i];while(head<=tail&&que[tail].val<=y) tail--;que[++tail]=Node(k,y);while(que[head].tag<k-num[i]) head++;dp[k*val[i]+j]=que[head].val+k*val[i];}}}printf("%d %d\n",sum-dp[sum1],dp[sum1]); }int main() {while(~scanf("%d",&n)){if(n<0) break;init();DP();}return 0; }還有二進制優化，請查看：http://www.cnblogs.com/RainingDays/archive/2013/05/01/3053274.html
http://acm.hdu.edu.cn/showproblem.php?pid=4374
具體代碼請查看：http://www.cnblogs.com/RainingDays/archive/2013/05/01/3053198.html
http://acm.hdu.edu.cn/showproblem.php?pid=3706
代碼：
#include <algorithm> #include <iostream> #include <limits.h> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set>using namespace std;const int maxn=10000+2;struct Node {int tag;int val;Node(int t=0,int v=0):tag(t),val(v){} }que[maxn];int main() {int n,a,b;while(~scanf("%d %d %d",&n,&a,&b)){int head,tail;__int64 sum=1,ans=1;head=tail=0;for(int i=1;i<=n;i++){sum=(sum%b*a%b)%b;while(head<tail&&que[tail-1].val>=sum) tail--;que[tail++]=Node(i,sum);while(head<tail&&que[head].tag<i-a) head++;ans=(ans%b*que[head].val%b)%b;}printf("%I64d\n",ans);}return 0; } View Code以下是單調隊列斜率優化：大家可以去做做看，題目都差不多有點類似的感覺。
http://acm.hdu.edu.cn/showproblem.php?pid=4258
代碼：
#include <algorithm> #include <iostream> #include <limits.h> #include <cstdlib> #include <cstring> #include <cstdio> #include <queue> #include <stack> #include <cmath> #include <map> #include <set>using namespace std;typedef __int64 int64;const int maxn=1000000+2; const int INF=0x3fffffff;int64 n,c,num[maxn]; int64 dp[maxn],que[maxn];void data_in() {for(int i=1;i<=n;i++)scanf("%I64d",&num[i]); }int64 getup(int i,int j) {return dp[i-1]+num[i]*num[i]-dp[j-1]-num[j]*num[j]; }int64 getdown(int i,int j) {return 2*(num[i]-num[j]); }void DP() {int head,tail;head=1,tail=0;for(int i=0;i<=n;i++) dp[i]=(i==0)?0:INF;for(int i=1;i<=n;i++){while(head<=tail&&getup(i,que[tail])*getdown(que[tail],que[tail-1])<=getup(que[tail],que[tail-1])*getdown(i,que[tail]))tail--;que[++tail]=i;while(head<=tail&&getup(que[head+1],que[head])<=num[i]*getdown(que[head+1],que[head])) head++;dp[i]=dp[que[head]-1]+c+(num[i]-num[que[head]])*(num[i]-num[que[head]]);}printf("%I64d\n",dp[n]); }int main() {while(scanf("%I64d %I64d",&n,&c),n+c){data_in();DP();}return 0; } View Codehttp://acm.hdu.edu.cn/showproblem.php?pid=2993
至于這個題的分析，在zy的的論文中已經很詳細了，在此不再贅述。
代碼：
#include <algorithm> #include <iostream> #include <limits.h> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <cmath> #include <queue> #include <stack> #include <map> #include <set>using namespace std;const int maxn=100000+5;int n,k,que[maxn]; int sum[maxn];inline bool scan_d(int &num) {char in;bool isn=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){isn=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10;num+=in-'0';}if(isn) num-=num;return true; }void data_in() {memset(sum,0,sizeof(int)*(n+1));for(int i=1;i<=n;i++){scan_d(sum[i]);sum[i]+=sum[i-1];} }inline double max(double a,double b) {return a<b?b:a; }double get(int x,int y) {return 1.0*(sum[x]-sum[y])/(x-y); }void DP() {int head,tail;double ma=0;head=1,tail=0;que[++tail]=0;for(int i=k;i<=n;i++){while(head<tail&&get(i-k,que[tail])<=get(que[tail],que[tail-1])) tail--;que[++tail]=i-k;while(head<tail&&get(i,que[head+1])>=get(i,que[head])) head++;ma=max(ma,get(i,que[head]));}printf("%.2lf\n",ma); }int main() {while(~scanf("%d %d",&n,&k)){data_in();DP();}return 0; } View Codehttp://acm.hdu.edu.cn/showproblem.php?pid=2829
這個題做的時候超惡心，因為發現自己一直用的單調隊列的模板發現有點問題，wa了好幾天。后來參考別人的寫法過的。
代碼：
#include <algorithm> #include <iostream> #include <limits.h> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set>using namespace std;const int maxn=1000+2; const int INF=0x7fffffff;int n,m; __int64 num[maxn],sumf[maxn],sum[maxn]; double dp[maxn][maxn]; int que[maxn];void data_in() {memset(sum,0,sizeof(sum));memset(sumf,0,sizeof(sumf));for(int i=0;i<=n+1;i++){for(int j=0;j<=m+1;j++){if(j==0) dp[i][j]=0;else dp[i][j]=INF;}}for(int i=1;i<=n;i++){scanf("%I64d",&num[i]);sum[i]=sum[i-1]+num[i];sumf[i]=sumf[i-1]+num[i]*num[i];dp[i][0]=(sum[i]*sum[i]-sumf[i])*1.0/2;} }double getup(int x,int y,int p) {return (2*dp[x][p-1]+sum[x]*sum[x]+sumf[x])-(2*dp[y][p-1]+sum[y]*sum[y]+sumf[y]); }__int64 getdown(int x,int y) {return sum[x]-sum[y]; }void DP() {for(int j=1;j<=m;j++){int head,tail;head=tail=0;que[tail++]=0;for(int i=j;i<=n;i++){while(head+1<tail&&getup(que[head+1],que[head],j)<=2*sum[i]*getdown(que[head+1],que[head])) head++;dp[i][j]=dp[que[head]][j-1]+((sum[i]-sum[que[head]])*(sum[i]-sum[que[head]])-(sumf[i]-sumf[que[head]]))/2;while(head+1<tail&&getup(i,que[tail-1],j)*getdown(que[tail-1],que[tail-2])<=getup(que[tail-1],que[tail-2],j)*getdown(i,que[tail-1]))tail--;que[tail++]=i;}}printf("%.0lf\n",dp[n][m]); }int main() {while(scanf("%d %d",&n,&m),n+m){data_in();DP();}return 0; } View Codehttp://acm.hdu.edu.cn/showproblem.php?pid=3507
代碼：
#include <algorithm> #include <iostream> #include <limits.h> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set>using namespace std;const int maxn=500000+5; const int INF=0x3fffffff;int n,m; int sum[maxn]; int dp[maxn]; int que[maxn];void data_in() {memset(sum,0,sizeof(sum));for(int i=1;i<=n;i++){scanf("%d",&sum[i]);sum[i]+=sum[i-1];} }int getup(int x,int y) {return (dp[x]+sum[x]*sum[x])-(dp[y]+sum[y]*sum[y]); }int getdown(int x,int y) {return 2*(sum[x]-sum[y]); }void DP() {int head,tail;head=1,tail=0;que[++tail]=0;for(int i=1;i<=n;i++){while(head<tail&&getup(que[head+1],que[head])<=sum[i]*getdown(que[head+1],que[head])) head++;dp[i]=dp[que[head]]+(sum[i]-sum[que[head]])*(sum[i]-sum[que[head]])+m;while(head<tail&&getup(i,que[tail])*getdown(que[tail],que[tail-1])<=getup(que[tail],que[tail-1])*getdown(i,que[tail]))tail--;que[++tail]=i;}printf("%d\n",dp[n]); }int main() {while(~scanf("%d %d",&n,&m)){data_in();DP();}return 0; } View Codehttp://acm.hdu.edu.cn/showproblem.php?pid=3480
代碼：
#include <algorithm> #include <iostream> #include <limits.h> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set>using namespace std;const int maxn=10000+2; const int maxm=5000+2; const int INF=0x3fffffff;int n,m; int num[maxn],que[maxn]; int dp[maxn][maxm];void init() {scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&num[i]);sort(num+1,num+1+n);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(j==1)dp[i][1]=(num[i]-num[1])*(num[i]-num[1]);else if(j==i)dp[i][j]=0;elsedp[i][j]=INF;}} }int getup(int x,int y,int p) {return dp[x][p-1]+num[x+1]*num[x+1]-(dp[y][p-1]+num[y+1]*num[y+1]); }int getdown(int x,int y) {return num[x+1]-num[y+1]; }int DP() {for(int j=2;j<=m;j++){int head,tail;head=tail=0;que[tail++]=j-1;for(int i=j;i<=n;i++){while(head+1<tail&&getup(que[head+1],que[head],j)<=2*num[i]*getdown(que[head+1],que[head])) head++;dp[i][j]=dp[que[head]][j-1]+(num[i]-num[que[head]+1])*(num[i]-num[que[head]+1]);while(head+1<tail&&getup(i,que[tail-1],j)*getdown(que[tail-1],que[tail-2])<=getup(que[tail-1],que[tail-2],j)*getdown(i,que[tail-1]))tail--;que[tail++]=i;}}return dp[n][m]; }int main() {int t;scanf("%d",&t);for(int i=1;i<=t;i++){init();printf("Case %d: %d\n",i,DP());}return 0; } View Codehttp://acm.hdu.edu.cn/showproblem.php?pid=3045
代碼：
#include <algorithm> #include <iostream> #include <limits.h> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set>using namespace std;const int maxn=400000+2; const int INF=0x3fffffff;int n,m; __int64 num[maxn],sum[maxn],que[maxn]; __int64 dp[maxn];void init() {for(int i=0;i<=n;i++)num[i]=sum[i]=0;for(int i=1;i<=n;i++)scanf("%I64d",&num[i]);sort(num+1,num+1+n);for(int i=1;i<=n;i++)sum[i]=sum[i-1]+num[i];for(int i=0;i<=n;i++)dp[i]=(i==0)?0:INF; }__int64 getup(int x,int y) {return dp[x]-sum[x]+x*num[x+1]-(dp[y]-sum[y]+y*num[y+1]); }__int64 getdown(int x,int y) {return num[x+1]-num[y+1];}void DP() {int head,tail;head=tail=0;que[tail++]=0;for(int i=1;i<=n;i++){while(head+1<tail&&getup(que[head+1],que[head])<=i*getdown(que[head+1],que[head])) head++;dp[i]=dp[que[head]]-sum[que[head]]+sum[i]-(i-que[head])*num[que[head]+1];if(i+1<2*m) continue;while(head+1<tail&&getup(i-m+1,que[tail-1])*getdown(que[tail-1],que[tail-2])<=getup(que[tail-1],que[tail-2])*getdown(i-m+1,que[tail-1]))tail--;que[tail++]=i-m+1;}printf("%I64d\n",dp[n]); }int main() {while(~scanf("%d %d",&n,&m)){init();DP();}return 0; } View Code終于好久之前就想寫的單調隊列在我胡亂貼鏈接，長篇大論的廢話中寫完了。>。<。。
善待每一天，努力做好自己。
歡迎轉載，注明出處。
轉載于:https://www.cnblogs.com/RainingDays/archive/2013/03/15/2961260.html
總結
- 上一篇： 光遇破碎季新物品有哪些?
- 下一篇： 模板概述