hdu 3183 A Magic Lamp（RMQ）
题意：将一个给定的数删除m位，求剩下的数的最小值分析：用RMQ，假设原来数字的长度为n，每次从一个区间里面取出一个最小值，取n-m即可
http://images.iyunv.com/OutliningIndicators/ContractedBlock.gifhttp://images.iyunv.com/OutliningIndicators/ExpandedBlockStart.gifView Code
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int n,dp;
char B;
void init_RMQ()
{
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
dp=i;
for(int j=1;j<log((double)(n))/log(2.0);j++)
{
int limit=n+1-(1<<j);
for(int i=0;i<limit;i++)
{
int x=dp;
int y=dp;
dp=B<=B?x:y;
}
}
}
int RMQ(int a,int b)
{
int k=(int)(log((double)(b-a+1))/log(2.0));
int x=dp;
int y=dp;
return B<=B?x:y;
}
int main()
{
int m,l,r;
char ans;
while(scanf("%s %d",B,&m)==2)
{
n=strlen(B);
init_RMQ();
m= n-m;
l=0;
r=n-m;
int t=m,len1=0;
while(t--)
{
l=RMQ(l,r);
r++;
ans=B;
l++;
//求出每一次取值的左右区间
}
ans='\0';
int flag=1;
for(int i=0;i<len1;i++)
{
if(flag && ans=='0')
continue;
flag=0;
printf("%c",ans);
}
if(flag)
puts("0");
else puts("");
}
return 0;
}
页:
[1]