首页 > 代码库 > HDU_3183_RMQ
HDU_3183_RMQ
http://acm.hdu.edu.cn/submit.php?pid=3183
初探rmq,这道题看了题解还是写了好久。原因是rmq处理字符串时没有自己写min函数,导致把返回的字符当成下标处理了。
这题也可以直接贪心写,思路和rmq一样,查找的方法效率低一些。
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;char a[1005],ans[1005];int dp[1005][20];int Min(int x,int y){ return a[x] <= a[y] ? x : y;}void rmq_init(int len){ for(int i = 0;i < len;i++) dp[i][0] = i; for(int j = 1;(1<<j) < len;j++) { for(int i = 0;i+(1<<j)-1 < len;i++) { dp[i][j] = Min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } }}int rmq_query(int l,int r){ int k = (int)(log((double)(r-l+1))/log(2.0)); return Min(dp[l][k],dp[r-(1<<k)+1][k]);}int main(){ int n,i; while(~scanf("%s%d",a,&n)) { int len = strlen(a); rmq_init(len); n = len-n; int pos = 0,num = 0; while(n) { pos = rmq_query(pos,len-n); ans[num++] = a[pos++]; n--; } for(i = 0;i < num && ans[i] == ‘0‘;i++); if(i == num) printf("0\n"); else { for(;i < num;i++) printf("%c",ans[i]); printf("\n"); } } return 0;}
HDU_3183_RMQ
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。