Sliding Window
2021-02-20 14:17
阅读：344
poj2823 Sliding Window
题目大意：给你一个n个数的序列，有一个长度固定的窗口，求出两个数列，分别是窗口从左滑到右，窗口内的最小值和最大值，分两行输出。
注释：n
想法：这内存是真恶心啊，正常的ST算法过不去，想到线段树，......咳咳，虽然这道题可以用单调队列和线段树没有什么障碍的A掉，但是今天我们仍然用ST维护RMQ来解决。首先，我们对内存有一定的限制，但是我们有一个极好的条件，那就是窗口的大小是固定的。所以，不难发现，我们所用到的f[i][j]数组只用到了最后一维，那么，我们想办法压维。压维最根本的是可否可行在于动态规划更新时是否有后效性。所以，我们就看一看。首先，我们显然知道，更新一个f的值所用到的，一定有一个是它自己，还有一个就是往后$2^{j-1}$所代表的值，不难发现，这两个下表都不小于i。所以，我们在从左向右松弛1-n时，所用到的下标都是没有被这一轮更新的，也就是说，是没有后效性的，故此，我们压维是可以的。所以，这道题就A掉了。
在此，我们有一个东西，就是log数组是不需要占用一个数组的内存的，我们发现，我们窗口固定时，log所提取的数也是固定的，那么我们就可以在预处理时顺便将log的值附好，即可。
最后，附上丑陋的代码... ...
1 #include2 #include 3 #include 4 #define N 1000010 5 using namespace std; 6 int a[N]; 7 int f[N],g[N]; 8 int main() 9 { 10 int n,len; 11 int maxlog; 12 while(~scanf("%d%d",&n,&len)) 13 { 14 // memset(f,0,sizeof(f)); 15 // memset(g,0,sizeof(g)); 16 for(int i=1;i"%d",&a[i]); 17 for(int i=1;i//初始化 18 { 19 f[i]=a[i]; 20 g[i]=a[i]; 21 } 22 maxlog=0;//这点贼重要，我们发现如果len==1,maxlog没有值??! 23 for(int i=1;(1) 24 { 25 maxlog=i; 26 for(int j=1;j+(11) 27 { 28 f[j]=max(f[j],f[j+(11))]); 29 g[j]=min(g[j],g[j+(11))]); 30 } 31 } 32 // cout33 // for(int i=1;i+(134 // { 35 // cout36 // } 37 for(int i=1;i1;i++) 38 { 39 printf("%d ",min(g[i],g[i+len-(1maxlog)])); 40 } 41 printf("\n");//别忘记分行 42 for(int i=1;i1;i++) 43 { 44 printf("%d ",max(f[i],f[i+len-(1maxlog)])); 45 } 46 printf("\n"); 47 } 48 }
小结：RMQ的点还有很多，还是那句话，倍增的想法的重要性要超过这个算法本身。
错误：1.maxlog的初始化，极其重要。
2.在初始化时，注意端点的位置。
评论
亲，登录后才可以留言！