算法"/>
st算法
st算法中的动态规划还不是完全理解,但是,就是因为这两个代码:
以下的文字:百度百科也讲的挺不错的
首先是预处理,用一个DP解决。设a[i]是要求区间最值的数列,f[i,j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。f[1,2]=5,f[1,3]=8,f[2,0]=2,f[2,1]=4……从这里可以看出f[i,0]其实就等于a[i]。这样,Dp的状态、初值都已经有了,剩下的就是状态转移方程。我们把f[i,j]平均分成两段(因为f[i,j]一定是偶数个数字),从i到i+2^(j-1)-1为一段,i+2^(j-1)到i+2^j-1为一段(长度都为2^(j-1))。用上例说明,当i=1,j=3时就是3,2,4,5 和 6,8,1,2这两段。f[i,j]就是这两段的最大值中的最大值。于是我们得到了动规方程
F[i,j]=max(F[i,j-1],F[i+2^(j-i),j-1]).
void rmq_isit(bool ok)
{ for(int i=1;i<=n;i++) mm[i][0]=mi[i][0]=a[i]; for(int j=1;(1<<j)<=n;j++) { for(int i=1;i+(1<<j)-1<=n;i++) { if(ok) mm[i][j]=max(mm[i][j-1],mm[i+(1<<(j-1))][j-1]); else mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]); } }
}
如果不是全部二分,也不用怕,最后在来一次比较,即求交叉部分。
那么查询的时候对于任意一个区间 l – r ,我们同样可以得到区间差值 len = (r - l + 1)。
那么我们这一用小于2^k<=len,的 k 把区间分成可以交叉的两部分l 到 l+2^(k)- 1, 到 r -(1<
int rmq(int l,int r)
{ int k=0; while((1<<(k+1))<=r-l+1) k++; //printf("%d %d %d %d\n",l,l+(1<<k),r-(1<<k)+1,r-(1<<k)+1+(1<<k)); int ans1=max(mm[l][k],mm[r-(1<<k)+1][k]); //交叉部分int ans2=min(mi[l][k],mi[r-(1<<k)+1][k]); return ans1-ans2;
}
更多推荐
st算法
发布评论