建网站的过程,快递公司网站制作,小语种网站案例,免费wordpress淘宝客主题单调队列#xff0c;即单调的队列。使用频率不高#xff0c;但在有些程序中会有非同寻常的作用。 动态规划单调队列的理解 做动态规划时常常会见到形如这样的转移方程#xff1a;f[x] max or min{g(k) | b[x] k x} w[x](其中b[x]随x单调不降#xff0c;即b[1]即单调的队列。使用频率不高但在有些程序中会有非同寻常的作用。 动态规划·单调队列的理解 做动态规划时常常会见到形如这样的转移方程 f[x] max or min{g(k) | b[x] k x} w[x] (其中b[x]随x单调不降即b[1]b[2]b[3]...b[n]) (g[k]表示一个和k或f[k]有关的函数w[x]表示一个和x有关的函数) 这个方程怎样求解呢我们注意到这样一个性质如果存在两个数j, k使得j k而且g(k) g(j)则决策j是毫无用处的。因为根据b[x]单调的特性如果j可以作为合法决策那么k一定可以作为合法决策并且k是一个比j要优的决策。因为k比j要优注意在这个经典模型中“优”是绝对的是与当前正在计算的状态无关的所以如果把待决策表中的决策按照k排序的话则g(k)必然是不降的。在此例中决策表即f[x]. 这样就引导我们使用一个单调队列来维护决策表。对于每一个状态f(x)来说计算过程分为以下几步 1、 队首元素出队直到队首元素在给定的范围中。 2、 此时队首元素就是状态f(x)的最优决策 3、 计算g(x)并将其插入到单调队列的尾部同时维持队列的单调性不断地出队直到队列单调为止。 重复上述步骤直到所有的函数值均被计算出来。不难看出这样的算法均摊时间复杂度是O(1)的。因此求解f(x)的时间复杂度从O(n^2)降到了O(n)。 以下来自某博客自己补充 我们从最简单的问题开始 给定一个长度为N的整数数列a(i),i0,1,...,N-1和窗长度k. 要求 f(i) max{a(i-k1),a(i-k2),..., a(i)},i 0,1,...,N-1 问题的另一种描述就是用一个长度为k的窗在整数数列上移动求窗里面所包含的数的最大值。 解法一 很直观的一种解法那就是从数列的开头将窗放上去然后找到这最开始的k个数的最大值然后窗最后移一个单元继续找到k个数中的最大值。 这种方法每求一个f(i),都要进行k-1次的比较复杂度为O(N*k)。 那么有没有更快一点的算法呢 解法二 我们知道上一种算法有一个地方是重复比较了就是在找当前的f(i)的时候i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢当然主要是i的前k-1个数中的最大值了。答案是可以这就要用到单调递减队列。 单调递减队列是这么一个队列它的头元素一直是队列当中的最大值而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素可以从队列的两端删除元素。 1.首先看插入元素为了保证队列的递减性我们在插入元素v的时候要将队尾的元素和v比较如果队尾的元素不大于v,则删除队尾的元素然后继续将新的队尾的元素与v比较直到队尾的元素大于v,这个时候我们才将v插入到队尾。 2.队尾的删除刚刚已经说了那么队首的元素什么时候删除呢由于我们只需要保存i的前k-1个元素中的最大值所以当队首的元素的索引或下标小于i-k1的时候就说明队首的元素对于求f(i)已经没有意义了因为它已经不在窗里面了。所以当index[队首元素]i-k1时将队首元素删除。 补充队列中的元素主要包括了两个性质大小--决定它是否影响f[i]的求值时效性删除队头使用--数组下标决定它是否已经离开了滑动窗口不在影响f[i]了,删除队尾时是新入队的时效性已在队中的元素了如果队尾的取值不如新入队的元素的值优的话那么就可以删除队尾了。 从上面的介绍当中我们知道单调队列与队列唯一的不同就在于它不仅要保存元素的值而且要保存元素的索引当然在实际应用中我们可以只需要保存索引而通过索引间接找到当前索引的值。 为了让读者更明白一点我举个简单的例子。 假设数列为8712516917246.N10,k3. 那么我们构造一个长度为3的单调递减队列 首先那8和它的索引0放入队列中我们用80表示每一步插入元素时队列中的元素如下 0插入8队列为80 1插入7队列为8071 2插入12队列为122 3插入5队列为12253 4插入16队列为164 5插入9队列为16495 。。。。依此类推 那么f(i)就是第i步时队列当中的首元素8812121616。。。 例题POJ 2823 滑动窗口 Sliding Window Time Limit: 12000MS Memory Limit: 65536KTotal Submissions: 54158 Accepted: 15543Case Time Limit: 5000MS Description An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is [1 3 -1 -3 5 3 6 7], and k is 3. Window positionMinimum valueMaximum value[1 3 -1] -3 5 3 6 7 -13 1 [3 -1 -3] 5 3 6 7 -33 1 3 [-1 -3 5] 3 6 7 -35 1 3 -1 [-3 5 3] 6 7 -35 1 3 -1 -3 [5 3 6] 7 36 1 3 -1 -3 5 [3 6 7]37Your task is to determine the maximum and minimum values in the sliding window at each position. Input The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line. Output There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values. Sample Input 8 3
1 3 -1 -3 5 3 6 7Sample Output -1 -3 -3 -3 3 3
3 3 5 5 6 7 1 #define N 10000052 #includeiostream3 #includecstring4 using namespace std;5 #includecstdio6 struct Pai{7 int val,pos;8 };9 Pai minque[N],maxque[N];
10 int minans[N],maxans[N],minhead,maxhead,mintail,maxtail,cur0;
11 int n,k;
12 int main()
13 {
14 scanf(%d%d,n,k);
15 int num;
16 minque[0].val(131)-1;
17 maxque[0].val(131)-1;
18 maxque[0].val*-1;
19 /*使用最大值最小值为了让que[0]会被后来的元素占用防止因为que[0]0的这个数代替了本来的最大值或者最小值所以一开始时会有mintail0,但是之后马上就mintail了没有访问数组所以不会有越界情况的。*/
20 for(int i1;ik;i)
21 {
22 scanf(%d,num);
23 while(minheadmintailminque[mintail].valnum) mintail--;
24 minque[mintail].valnum;
25 minque[mintail].posi;
26 while(maxheadmaxtailmaxque[maxtail].valnum) maxtail--;
27 maxque[maxtail].valnum;
28 maxque[maxtail].posi;
29 }
30 for(int ik1;in;i)
31 {
32 minans[cur]minque[minhead].val;
33 maxans[cur]maxque[maxhead].val;
34 scanf(%d,num);
35
36 while(minheadmintaili-minque[minhead].posk)minhead;
37 while(minheadmintailminque[mintail].valnum) mintail--;
38 minque[mintail].valnum;
39 minque[mintail].posi;
40
41 while(maxheadmaxtaili-maxque[maxhead].posk)maxhead;
42 while(maxheadmaxtailmaxque[maxtail].valnum) maxtail--;
43 maxque[maxtail].valnum;
44 maxque[maxtail].posi;
45 }
46 minans[cur]minque[minhead].val;
47 maxans[cur]maxque[maxhead].val;
48 for(int i1;icur;i)
49 printf(%d ,minans[i]);
50 printf(\n);
51 for(int i1;icur;i)
52 printf(%d ,maxans[i]);
53 return 0;
54 } 转载于:https://www.cnblogs.com/c1299401227/p/5774133.html
