http://acm.hdu.edu.cn/showproblem.php?pid=3183
题意：给出一个数，可以删除掉其中m个字符，要使得最后的数字最小，输出最后的数字（忽略前导零）。
思路：设数的长度为n，那么我们要删除其中m个最大的字符，可以转化为我们保留其中的n-m个最小的字符。对于第一个数，它存在的区间必定在[1,m+1]里面，因为我们要保证后面[m+2,n]区间有n-m-1个字符。当找到第一个数的下标为tmp的时候，第二个数的区间就是[tmp+1,m+2]……以此类推，直到找到最后。
这里我们就可以用RMQ来处理了。dp数组保存的信息是下标。
注意最后可能有前导零，要去除掉前导零。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7 #define N 50010 8 char s[1010]; 9 int dp[1010][20]; 10 int ans[1010]; 11 int n, m; 12 13 void Init() { 14 int k = (int)(log(n) / log(2)); 15 for(int i = 1; i <= n; i++) dp[i][0] = i; 16 for(int j = 1; j <= k; j++) 17 for(int i = 1; i + (1 << j) - 1 <= n; i++) 18 if(s[dp[i][j-1]] <= s[dp[i+(1<<(j-1))][j-1]]) dp[i][j] = dp[i][j-1]; 19 else dp[i][j] = dp[i+(1<<(j-1))][j-1]; 20 } 21 22 int Query(int l, int r) { 23 int k = (int)(log(r - l + 1) / log(2)); 24 return s[dp[l][k]] <= s[dp[r-(1<<k)+1][k]] ? dp[l][k] : dp[r-(1<<k)+1][k]; 25 } 26 27 int main() { 28 while(~scanf("%s%d", s + 1, &m)) { 29 n = strlen(s + 1); 30 Init(); 31 int cnt = 0, tmp = 1; 32 for(int i = 1; i <= n - m; i++) { 33 tmp = Query(tmp, m + i); 34 ans[++cnt] = s[tmp++] - ‘0‘; 35 } 36 for(tmp = 1; tmp <= cnt; tmp++) if(ans[tmp] != 0) break; 37 if(tmp > cnt) puts("0"); 38 else { for(; tmp <= cnt; tmp++) printf("%d", ans[tmp]); puts(""); } 39 } 40 return 0; 41 }
原文：http://www.cnblogs.com/fightfordream/p/6347392.html