首先考虑对于n个数字组成的数，只删除1位的情况。
比如176832，删除一位使得剩下的数值最小。结果是删除7而不是删除8所以可知并不总是删除最大的那个数字。
一种可行的贪心策略是：对于n位数构成的数删除m位，每次总是删除这样的a[i]：它是第一个a[i]>a[i+1]的数，如果不存在则就删除a[n]。如何证明给贪心策略是正确的呢？
假设始终不删除a[i]，那么最终m位数就必然包含a[i]。但其实a[i]>a[i+1]，所以我们完全可以删除a[i]，然后让a[i+1]在a[i]最终的位置上，那么得到的m位数自然更小了。所以a[i]必定要被删除的。以此类推，贪心得证。
RMQ：
因为要找n-m个数，删除m个数。所以原数的第1位到m+1位的数字中最小的那位（假设是第i位）肯定是n-m位数的第一位。（想想为什么）
这样我们就找到了第一位a[i]，接下来我们在从第i+1位数到m+2位数中找最小的那位，这个肯定是n-m位数的第二位。
以此类推，找够n-m位即可。
RMQ函数要做点修改。dmin[i][j]=k表示的是区间[i，i+(1<<j)-1]内最小值的下标而不是值了。
///1085422276 #include<bits/stdc++.h> using namespace std ; typedef long long ll; #define mem(a) memset(a,0,sizeof(a)) inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘)f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*f; } //**************************************** #define maxn 1999+5 #define mod 1000000007 int dp[maxn][200],k,len; char a[maxn]; int Min(int x,int y){ return a[x]<=a[y]?x:y; } void RMQ_init(){ mem(dp); for(int i=0;i<len;i++){ dp[i][0]=i; } for(int i=1;(1<<i)<len;i++){ for(int j=0;(j+(1<<i)-1)<len;j++){ dp[j][i]=Min(dp[j][i-1],dp[j+(1<<(i-1))][i-1]); } } } int Q_RMQ(int l,int r){ int kk=(int)(log((double)(r-l+1))/log(2.0)); return Min(dp[l][kk],dp[r-(1<<kk)+1][kk]); }vector<int >ans; int main(){ while(scanf("%s%d",a,&k)!=EOF){ len=strlen(a);ans.clear(); RMQ_init();//cout<<1<<endl; k=len-k;int pos=0; while(k--){ pos=Q_RMQ(pos,len-k-1); ans.push_back(pos); pos=pos+1; }bool bo=0;bool flag=0; for(int i=0;i<ans.size();i++){ if(flag){ cout<<a[ans[i]];bo=1;flag=1; } else if(a[ans[i]]!=‘0‘){flag=1;cout<<a[ans[i]];bo=1;} }if(!bo)cout<<0<<endl; else cout<<endl; } return 0; }
原文：http://www.cnblogs.com/zxhl/p/4944978.html
