多用户分布式网站开发,商丘免费网站建设开发公司,长春微信做网站,国家企业信用公信系统入口因为一直在听身边的人说什么单调队列/斜率优化dp/背包#xff0c;(ps:我也不清楚这样称呼对不对#xff0c;因为我真心是没见过这些东西)我都觉得那是神一样的东西。终于抽出时间学了一下。 昨天在朋友一本书里面看到一句话#xff0c;这里先跟大家分享一下#xff1a; 没有… 因为一直在听身边的人说什么单调队列/斜率优化dp/背包(ps:我也不清楚这样称呼对不对因为我真心是没见过这些东西)我都觉得那是神一样的东西。终于抽出时间学了一下。 昨天在朋友一本书里面看到一句话这里先跟大家分享一下 没有人会带你人要是没有学会自立那么将一无所能;如果过于自立那也将一无所立. -----柯林斯 想想自己自学了这么长时间却是内心的真实写照。 一直觉得自己特别失败这么长时间了还是一无所成没拿什么牌没学过多么高深的东西现在已是迟暮之年的猥琐学子不晓得前途在何方。而且队伍还残了。。。 ------------------------------2013.3.15 更 我终于刷完了杭电上面单调队列的题其中有有一些简单的单调队列题目还有一些背包动归的优化下面的内容我都一一为大家奉上ps我的刷题顺序是通过百度“hdu 单调队列”不是由易到难 http://acm.hdu.edu.cn/showproblem.php?pid3415 题意给定一个长度为n的环形序列让你从中找出一个k长的子序列使得这段序列的和是所有k长子序列中和最大的那个输出和并输出得到这个和时的起始位置跟终止位置。 思路因为还要记录起始位置跟终止位置所以很显然队列结点还需要记录下标。我们用一个单调减队列来维护到当前下标时前面sum的最小值当然还需要head使得长度控制在k的范围内。循环判断更新最大值并记录相应下标就可以了。 View Code #include algorithm
#include iostream
#include cstdlib
#include cstring
#include cstdio
#include queue
#include mapusing namespace std;const int maxn1000005;int a[maxn],sum[maxn1],head,tail,n,k,st,ed,ans;
struct node
{int val;int tag;node(int v0,int t0):val(v),tag(t){}
}q[maxn1];void data_in()
{memset(sum,0,sizeof(sum));memset(a,0,sizeof(a));for(int i1;in;i){scanf(%d,a[i]);sum[i]sum[i-1]a[i];}for(int in1;ink;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();head1;tail1;q[tail]node(0,1);sted1;anssum[1];for(int i2;ink;i){while(headtailq[tail].valsum[i-1]) tail--;q[tail]node(sum[i-1],i);while(headtailq[head].tagi-k) head;int tmpsum[i]-q[head].val;if(tmpans){anstmp;stq[head].tag;edi;}}if(stn) st-n;if(edn) ed-n;printf(%d %d %d\n,ans,st,ed);}return 0;
} http://acm.hdu.edu.cn/showproblem.php?pid3474 题意可以抽象成给一个只由1和-1组成的循环序列让你求以每个点为起点且长度串长的子串的最小值。 思路贴一个好题解:http://blog.csdn.net/xymscau/article/details/6677427 http://acm.hdu.edu.cn/showproblem.php?pid3530 题意在一个序列中找一个最长的子序列使之满足其最大值跟最小值之差valmvalk输出该子序列的长度。 思路显然维护一个单调增队列跟单调减队列如果队首元素之差满足条件的时候就更新不满足的时候相应指针移动并用中间变量start记录一下该序列的起始位置更新长度即可。 代码 View Code #include algorithm
#include iostream
#include cstdlib
#include cstring
#include cstdio
#include queue
#include vector
#include mapusing namespace std;const int maxn1000005;int n,m,k,head1,head2,tail1,tail2,start;struct node
{int val;int tag;node(int v0,int t0):val(v),tag(t){}
}q[2][maxn];int main()
{int ans;while(~scanf(%d %d %d,n,m,k)){node tmp;head1head2start1,tail1tail2ans0;for(int i1;in;i){scanf(%d,tmp.val);tmp.tagi;while(head1tail1q[0][tail1].valtmp.val) tail1--;//最大q[0][tail1]node(tmp);while(head2tail2q[1][tail2].valtmp.val) tail2--;//最小q[1][tail2]node(tmp);while(q[0][head1].val-q[1][head2].valk){startmin(q[0][head1].tag,q[1][head2].tag);startq[0][head1].tag?head1:head2;start;}if(q[0][head1].val-q[1][head2].valmq[0][head1].val-q[1][head2].valk)ansmax(ans,i-start1);}printf(%d\n,ans);}return 0;
} 单调队列优化 http://acm.hdu.edu.cn/showproblem.php?pid1171 又把这个题用单调队列做了一遍代码 View Code #include algorithm
#include iostream
#include cstdlib
#include cstring
#include cstdiousing namespace std;const int maxn55;int n,sum,val[maxn],num[maxn];
struct Node
{int tag;int val;Node(int t0,int v0):tag(t),val(v){};
}que[250005];void init()
{sum0;for(int i1;in;i){scanf(%d %d,val[i],num[i]);sumval[i]*num[i];}
}inline int max(int a,int b)
{return ab?b:a;
}inline int min(int a,int b)
{return ab?a:b;
}int dp[250005];
void DP()
{memset(dp,0,sizeof(dp));int sum1sum/2;for(int i1;in;i){num[i]min(num[i],sum1/val[i]);for(int j0;jval[i];j){int head,tail;head1,tail0;for(int k0;k(sum1-j)/val[i];k){int ydp[k*val[i]j]-k*val[i];while(headtailque[tail].valy) tail--;que[tail]Node(k,y);while(que[head].tagk-num[i]) head;dp[k*val[i]j]que[head].valk*val[i];}}}printf(%d %d\n,sum-dp[sum1],dp[sum1]);
}int main()
{while(~scanf(%d,n)){if(n0) break;init();DP();}return 0;
} 还有二进制优化请查看http://www.cnblogs.com/RainingDays/archive/2013/05/01/3053274.html http://acm.hdu.edu.cn/showproblem.php?pid4374 具体代码请查看http://www.cnblogs.com/RainingDays/archive/2013/05/01/3053198.html http://acm.hdu.edu.cn/showproblem.php?pid3706 代码 #include algorithm
#include iostream
#include limits.h
#include cstdlib
#include cstring
#include cstdio
#include cmath
#include queue
#include stack
#include map
#include setusing namespace std;const int maxn100002;struct Node
{int tag;int val;Node(int t0,int v0):tag(t),val(v){}
}que[maxn];int main()
{int n,a,b;while(~scanf(%d %d %d,n,a,b)){int head,tail;__int64 sum1,ans1;headtail0;for(int i1;in;i){sum(sum%b*a%b)%b;while(headtailque[tail-1].valsum) tail--;que[tail]Node(i,sum);while(headtailque[head].tagi-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?pid4258 代码 #include algorithm
#include iostream
#include limits.h
#include cstdlib
#include cstring
#include cstdio
#include queue
#include stack
#include cmath
#include map
#include setusing namespace std;typedef __int64 int64;const int maxn10000002;
const int INF0x3fffffff;int64 n,c,num[maxn];
int64 dp[maxn],que[maxn];void data_in()
{for(int i1;in;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;head1,tail0;for(int i0;in;i) dp[i](i0)?0:INF;for(int i1;in;i){while(headtailgetup(i,que[tail])*getdown(que[tail],que[tail-1])getup(que[tail],que[tail-1])*getdown(i,que[tail]))tail--;que[tail]i;while(headtailgetup(que[head1],que[head])num[i]*getdown(que[head1],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),nc){data_in();DP();}return 0;
} View Code http://acm.hdu.edu.cn/showproblem.php?pid2993 至于这个题的分析在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 setusing namespace std;const int maxn1000005;int n,k,que[maxn];
int sum[maxn];inline bool scan_d(int num)
{char in;bool isnfalse;ingetchar();if(inEOF) return false;while(in!-(in0||in9)) ingetchar();if(in-){isntrue;num0;}else numin-0;while(ingetchar(),in0in9){num*10;numin-0;}if(isn) num-num;return true;
}void data_in()
{memset(sum,0,sizeof(int)*(n1));for(int i1;in;i){scan_d(sum[i]);sum[i]sum[i-1];}
}inline double max(double a,double b)
{return ab?b:a;
}double get(int x,int y)
{return 1.0*(sum[x]-sum[y])/(x-y);
}void DP()
{int head,tail;double ma0;head1,tail0;que[tail]0;for(int ik;in;i){while(headtailget(i-k,que[tail])get(que[tail],que[tail-1])) tail--;que[tail]i-k;while(headtailget(i,que[head1])get(i,que[head])) head;mamax(ma,get(i,que[head]));}printf(%.2lf\n,ma);
}int main()
{while(~scanf(%d %d,n,k)){data_in();DP();}return 0;
} View Code http://acm.hdu.edu.cn/showproblem.php?pid2829 这个题做的时候超恶心因为发现自己一直用的单调队列的模板发现有点问题wa了好几天。后来参考别人的写法过的。 代码 #include algorithm
#include iostream
#include limits.h
#include cstdlib
#include cstring
#include cstdio
#include cmath
#include queue
#include stack
#include map
#include setusing namespace std;const int maxn10002;
const int INF0x7fffffff;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 i0;in1;i){for(int j0;jm1;j){if(j0) dp[i][j]0;else dp[i][j]INF;}}for(int i1;in;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 j1;jm;j){int head,tail;headtail0;que[tail]0;for(int ij;in;i){while(head1tailgetup(que[head1],que[head],j)2*sum[i]*getdown(que[head1],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(head1tailgetup(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),nm){data_in();DP();}return 0;
} View Code http://acm.hdu.edu.cn/showproblem.php?pid3507 代码 #include algorithm
#include iostream
#include limits.h
#include cstdlib
#include cstring
#include cstdio
#include cmath
#include queue
#include stack
#include map
#include setusing namespace std;const int maxn5000005;
const int INF0x3fffffff;int n,m;
int sum[maxn];
int dp[maxn];
int que[maxn];void data_in()
{memset(sum,0,sizeof(sum));for(int i1;in;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;head1,tail0;que[tail]0;for(int i1;in;i){while(headtailgetup(que[head1],que[head])sum[i]*getdown(que[head1],que[head])) head;dp[i]dp[que[head]](sum[i]-sum[que[head]])*(sum[i]-sum[que[head]])m;while(headtailgetup(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 Code http://acm.hdu.edu.cn/showproblem.php?pid3480 代码 #include algorithm
#include iostream
#include limits.h
#include cstdlib
#include cstring
#include cstdio
#include cmath
#include queue
#include stack
#include map
#include setusing namespace std;const int maxn100002;
const int maxm50002;
const int INF0x3fffffff;int n,m;
int num[maxn],que[maxn];
int dp[maxn][maxm];void init()
{scanf(%d %d,n,m);for(int i1;in;i)scanf(%d,num[i]);sort(num1,num1n);for(int i1;in;i){for(int j1;jm;j){if(j1)dp[i][1](num[i]-num[1])*(num[i]-num[1]);else if(ji)dp[i][j]0;elsedp[i][j]INF;}}
}int getup(int x,int y,int p)
{return dp[x][p-1]num[x1]*num[x1]-(dp[y][p-1]num[y1]*num[y1]);
}int getdown(int x,int y)
{return num[x1]-num[y1];
}int DP()
{for(int j2;jm;j){int head,tail;headtail0;que[tail]j-1;for(int ij;in;i){while(head1tailgetup(que[head1],que[head],j)2*num[i]*getdown(que[head1],que[head])) head;dp[i][j]dp[que[head]][j-1](num[i]-num[que[head]1])*(num[i]-num[que[head]1]);while(head1tailgetup(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 i1;it;i){init();printf(Case %d: %d\n,i,DP());}return 0;
} View Code http://acm.hdu.edu.cn/showproblem.php?pid3045 代码 #include algorithm
#include iostream
#include limits.h
#include cstdlib
#include cstring
#include cstdio
#include cmath
#include queue
#include stack
#include map
#include setusing namespace std;const int maxn4000002;
const int INF0x3fffffff;int n,m;
__int64 num[maxn],sum[maxn],que[maxn];
__int64 dp[maxn];void init()
{for(int i0;in;i)num[i]sum[i]0;for(int i1;in;i)scanf(%I64d,num[i]);sort(num1,num1n);for(int i1;in;i)sum[i]sum[i-1]num[i];for(int i0;in;i)dp[i](i0)?0:INF;
}__int64 getup(int x,int y)
{return dp[x]-sum[x]x*num[x1]-(dp[y]-sum[y]y*num[y1]);
}__int64 getdown(int x,int y)
{return num[x1]-num[y1];}void DP()
{int head,tail;headtail0;que[tail]0;for(int i1;in;i){while(head1tailgetup(que[head1],que[head])i*getdown(que[head1],que[head])) head;dp[i]dp[que[head]]-sum[que[head]]sum[i]-(i-que[head])*num[que[head]1];if(i12*m) continue;while(head1tailgetup(i-m1,que[tail-1])*getdown(que[tail-1],que[tail-2])getup(que[tail-1],que[tail-2])*getdown(i-m1,que[tail-1]))tail--;que[tail]i-m1;}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
