?題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3183
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> /** 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<<j) < len; j++)for(int i = 0; i+(1<<j)-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<<k)+1][k]); }int main() {int len;while(scanf("%s%d",num,&t)!=EOF){len = strlen(num);rmq_init(len);int m = len-t;int p = 0,j=0;while(m--){p=query(p,len-m-1);res[j++] = num[p++];}for(p = 0; p < j; p++)if(res[p]!='0')break;if(p==j)printf("0");else{while(p<j)printf("%c",res[p++]);}puts("");}return 0; }
?
