poj 3264 Balanced Lineup-白红宇

poj 3264 Balanced Lineup

阅读量：4971 次

发布时间：2019-06-12

本文共 1209 字，大约阅读时间需要 4 分钟。

福建农林大学 FAFU poj也有一题和这题差不多的，可以去尝试看看

http://acm.fafu.edu.cn/problem.php?id=1272

RMQ poj 3264 Balanced Lineup

//poj 3264 Balanced Lineup//RMQ//用RMQ求出最大值和最小值相减即可，具体看一下代码//学RMQ可以看着个博客http://blog.csdn.net/ice2013/article/details/7545143//写的挺不错的//预处理，//动归求出dp_max[i][j]和dp_min[i][j],dp表示从i开始的2^j个数中的最值,//2^j一定是偶数,所以把它分为 [i,i+2^(j-1)-1]和[i+2^(j-1), i+2^j -1]这两个区间,//则dp[i][j]即从这两个区间得出,即dp[i][j] = max(dp[i][1<<(j-1)], dp[i+(1<<(j-1)][j-1])//询问[a,b]时先求出tmp = log(b-a+1)/log(2.0)//然后求max(dp[a][tmp], dp[b-(1<
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define comein freopen("in.txt", "r", stdin);#define N 50005#define INF 1<<30#define eps 1e-5int dp_max[N][20], dp_min[N][20];void init(int n_cow){                   //n_cow可以表示成2 的几次方，换底公式    int index = log(n_cow * 1.0) / log(2.0);    for(int j = 1; j <= index; ++j)    {       //i ~ i+(1<
          
            to)            {                from ^= to;                to ^= from;                from ^= to;            }            printf("%d\n", RMQ(from, to));        }    }    return 0;}