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数组保存的信息是下标。
注意最后可能有前导零，要去除掉前导零。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define N 50010
char s[];
int dp[][];
int ans[];
int n, m; void Init() {
int k = (int)(log(n) / log());
for(int i = ; i <= n; i++) dp[i][] = i;
for(int j = ; j <= k; j++)
for(int i = ; i + ( << j) - <= n; i++)
if(s[dp[i][j-]] <= s[dp[i+(<<(j-))][j-]]) dp[i][j] = dp[i][j-];
else dp[i][j] = dp[i+(<<(j-))][j-];
} int Query(int l, int r) {
int k = (int)(log(r - l + ) / log());
return s[dp[l][k]] <= s[dp[r-(<<k)+][k]] ? dp[l][k] : dp[r-(<<k)+][k];
} int main() {
while(~scanf("%s%d", s + , &m)) {
n = strlen(s + );
Init();
int cnt = , tmp = ;
for(int i = ; i <= n - m; i++) {
tmp = Query(tmp, m + i);
ans[++cnt] = s[tmp++] - '';
}
for(tmp = ; tmp <= cnt; tmp++) if(ans[tmp] != ) break;
if(tmp > cnt) puts("");
else { for(; tmp <= cnt; tmp++) printf("%d", ans[tmp]); puts(""); }
}
return ;
}