首页 > 代码库 > HDU_3183_RMQ

HDU_3183_RMQ

http://acm.hdu.edu.cn/submit.php?pid=3183

 

初探rmq,这道题看了题解还是写了好久。原因是rmq处理字符串时没有自己写min函数,导致把返回的字符当成下标处理了。

这题也可以直接贪心写,思路和rmq一样,查找的方法效率低一些。

 

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;char a[1005],ans[1005];int dp[1005][20];int Min(int x,int y){    return a[x] <= a[y] ? x : y;}void rmq_init(int len){    for(int i = 0;i < len;i++)  dp[i][0] = i;    for(int j = 1;(1<<j) < len;j++)    {        for(int i = 0;i+(1<<j)-1 < len;i++)        {            dp[i][j] = Min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);        }    }}int rmq_query(int l,int r){    int k = (int)(log((double)(r-l+1))/log(2.0));    return Min(dp[l][k],dp[r-(1<<k)+1][k]);}int main(){    int n,i;    while(~scanf("%s%d",a,&n))    {        int len = strlen(a);        rmq_init(len);        n = len-n;        int pos = 0,num = 0;        while(n)        {            pos = rmq_query(pos,len-n);            ans[num++] = a[pos++];            n--;        }        for(i = 0;i < num && ans[i] == 0;i++);        if(i == num)    printf("0\n");        else        {            for(;i < num;i++)   printf("%c",ans[i]);            printf("\n");        }    }    return 0;}

 

HDU_3183_RMQ