题目链接:
#include#include #include #include /**rmq 问题:题意很简单,求一行数字中除去其中m个数字,使其组成最小的一个数字使用rmq解题,设源数字长为n,那么除去m个数字后剩下的还剩n-m个数字,组成最小的数字。(1)因为剩下n-m个数字,那么在1到m+1位置中最小的那个数字必是结果中的第一个数字i,(2)然后从这个数字i位置的下个位置i+1开始到m+2位置的数字中最小的那个数字必定是结果中第二个数字,以此类推下去向后找。(3)为了保证数字最小所以要保证高位最小还要保证数字长度够用~~**/char num[1010];char res[1020];int dp_min[1010][20];int t;//返回较小值int mins(int a,int b){ return num[a]<=num[b]?a:b;}void rmq_init(int len){ for(int i = 0; i < len; i++) dp_min[i][0] = i; for(int j = 1; (1< < len; j++) for(int i = 0; i+(1< < len;i++) dp_min[i][j] = mins(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]);}int query(int l,int r){ int k = (int)(log((double)(r-l+1))/log(2.0)); return mins(dp_min[l][k],dp_min[r-(1<