列举网免费发布信息网/克州seo整站排名

题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。

输入格式
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。

第二行为m个数,分别是账目的钱数

后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。

输出格式
输出文件中为每个问题的答案。具体查看样例。

输入输出样例
输入 #1复制
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10
输出 #1复制
2 3 1

思路：

1. dp[i][j]代表i ~ i + 2^j - 1的最小值。那么子状态就是dp[i][j-1],dp[i + (1 << (j-1))][j-1]。分别代表i ~ i + 2^(j-1) -1 。 i + 2的j-1次方 ~ i + 2的j次方 - 1.
2. 2^log(a)>a/2 。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>using namespace std;int dp[100010][30],a[100010];
int main()
{int t = log2(5);printf("%d ",(1 << t));int n,m;scanf("%d%d",&m,&n);for(int i = 1;i <= m;i++){scanf("%d",&a[i]);dp[i][0] = a[i];}for(int j = 1;j <= 20;j++){for(int i = 1;i <= m;i++){if(i + (1 << j) - 1 <= m){dp[i][j] = min(dp[i + (1 << (j - 1))][j - 1],dp[i][j - 1]);}}}for(int i = 1;i <= n;i++){int x,y;scanf("%d%d",&x,&y);int t = log(y - x + 1) / log(2);printf("%d ",min(dp[x][t],dp[y - (1 << t) + 1][t]));}return 0;
}