hdu3183 rmq求区间最值的下标

两个月前做的题，以后可以看看，是rmq关于求区间最值的下标

/*

hdu3183

终点

给一个整数，可以删除m位，留下的数字形成一个新的整数

rmq

取n-m个数，使形成的数最小

*/

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#define MAXN 1010

using namespace std;

int dp[MAXN][];

int a[MAXN];

void makeRMQ(int n,int b[]){//在i到1<<j区间内的最小值的下标

    for(int i=;i<n;i++)

        dp[i][]=i;//区间长度等于0时

    for(int j=;(<<j)-<n;j++)

        for(int i=;i+(<<j)-<n;i++)

            if(b[dp[i][j-]]<=b[dp[i+(<<j-)][j-]])

            //这里一定要加等号，就是相等的时候取下标小的

                dp[i][j]=dp[i][j-];

            else

                dp[i][j]=dp[i+(<<j-)][j-];

}

int rmqIndex(int s,int v,int b[]){//在区间s->v之间找区间最小值，

                                    //加等号，取小标小的

    //1<<k+1的长度必须覆盖[s,v]

    int k=(int)(log(v-s+1.0)/log(2.0));//k就是那个区间[s,v]长度的log2

    if (b[dp[s][k]]<=b[dp[v-(<<k)+][k]])

        return dp[s][k];

    else

        return dp[v-(<<k)+][k];

}

char str[MAXN];

int ans[MAXN];

int main(){

    int m;

    while(scanf("%s%d",&str,&m)!=EOF){

        int n=strlen(str);

        for(int i=;i<n;i++)

            a[i]=str[i]-'';

        makeRMQ(n,a);

        int t=;

        int temp=;//temp最后=n-m

        //找n-m个数，每次从[t,i]中找到最小的

        for(int i=m;i<n;i++){

            t=rmqIndex(t,i,a);

            ans[temp++]=a[t++];

        }

        t=;

        while(t<temp&&ans[t]==)

            t++;//=滤掉高位的0！

        if(t>=temp)

            printf("0\n");

        else{

            for(int i=t;i<temp;i++)

                printf("%d",ans[i]);

            printf("\n");

        }

    }

    return ;

}