【HDOJ】3183 A Magic Lamp

jackfya

　　RMQ。



1 /* 3183 */
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5
6 #define MAXN 1005
7
8 char s[MAXN], ans[MAXN];
9 int dp[MAXN][MAXN];
10 int n,len,m;
11
12 int min(int x, int y) {
13     return s[x]<=s[y] ? x:y;
14 }
15
16 void RMQ_init() {
17     int i, j, k;
18
19     for (i=1; i<=len; ++i)
20         dp[0] = i;
21     for (j=1; (1<<j)<=len; ++j)
22         for (i=1; i+(1<<j)-1<=len; ++i)
23             dp[j] = min(dp[j-1], dp[i+(1<<(j-1))][j-1]);
24 }
25
26 int RMQ(int l, int r) {
27     int k = 0;
28
29     while ((1<<(k+1)) <= r-l+1)
30         ++k;
31     return min(dp[l][k], dp[r-(1<<k)+1][k]);
32 }
33
34 int main() {
35     int i, j, k;
36     int l;
37
38     #ifndef ONLINE_JUDGE
39         freopen("data.in", "r", stdin);
40         freopen("data.out", "w", stdout);
41     #endif
42
43     while (scanf("%s %d", s+1, &m)!=EOF) {
44         len = strlen(s+1);
45         RMQ_init();
46         m = len - m;
47         l = k = 1;
48         while (m--) {
49             k = RMQ(k, len-m);
50             ans[l++] = s[k++];
51         }
52         for (i=1; i<l; ++i)
53             if (ans != '0')
54                 break;
55         ans[l] = '\0';
56         if (i == l)
57             puts("0");
58         else
59             puts(ans+i);
60     }
61
62     return 0;
63 }