hdu3183 A Magic Lamp【ST算法】

给你一个数，不超过2000位，让你删去其中m位数字，删除完后，剩下的数字顺序不变，求怎么删除数字最小。

这道题是一道ST表入门题目。

首先先来介绍一波ST：

ST表算法详解（求最小值）： 
用mn[i][j]表示从j到j+2^i-1的最小值（长度显然为2^i）。 
任意一段的最小值显然等于min（前半段最小值，后半段最小值）。 
那么mn[i][j]如何用其他状态来继承呢？ 
j到j+2^i-1的长度为2^i，那么一半的长度就等于2^(i-1)。 
那么前半段的状态表示为mn[i-1][j]。 
后半段的长度也为2^(i-1)，起始位置为j+2^(i-1)。 
那么后半段的状态表示为mn[i-1][j+2^(i-1)]。 
所以： 
mn[i][j]=min(mn[i-1][j],mn[i-1][j+2^(i-1)]。
线段树预处理O（nlogn），查询O（logn），支持在线修改 
ST表预处理O（nlogn），查询O（1），但不支持在线修改 

题解：

这个数如果有n位，要删除m个，那么第一个只能在第1位到第n-m-1位，第二个则是在第2到第n-m，以此类推， 求出这些区间内的最小值即可。

题目链接

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

int f[2005][2005];
char ss[2005], num[2005];
int m, n;

int min(int i,int j) {//比较字符大小 
	return ss[i]<=ss[j] ? i:j;
}

void ST() {
	int i, j;
	for(int i = 0; i < n; i++) {
		f[i][0] = i; //初始化 每个长度为1的区间初始值为其本身
	}
	for(j = 1; j <= (int)(log((double)n)/log(2.0)); j++) {
		for(i=0; i+(1<<j)-1<n; i++) {
			f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);
		}

	}
}

int que(int l, int r) {//查询区间 
	int x = (int)(log((double)(r-l+1))/log(2.0));
	return min(f[l][x], f[r-(1<<x)+1][x]);
}
int main() {
	while(~scanf("%s%d", ss, &m)) {
		n = strlen(ss);
		m = n - m;
		ST();
		int i = 0;
		int j = 0;
		while(m--) {//查找区间最小值
			i = que(i, n-m-1);
			num[j++] = ss[i++];
		}
		for(i = 0; i < j; i++) { //判断第一个0的位置
			if(num[i] != '0') {
				break;
			}
		}
		if(i == j) { //如果每一位都为0，则直接输出打印0
			printf("0\n");
			continue;
		}
		while(i < j) {
			printf("%c",num[i]);//从第一个不为0的数开始打印
			i++;
		}
		printf("\n");
	}
	return 0;
}