CF 335B. Palindrome(DP)

挺好玩的一个题，1Y。。。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 int dp[2601][2601];
 6 char s1[50001];
 7 char s2[50001];
 8 int o[26];
 9 char que[5001];
10 int main()
11 {
12     int i,j,len,a,b,num;
13     scanf("%s",s1);
14     len = strlen(s1);
15     for(i = 0; i < len; i ++)
16     {
17         o[s1[i]-'a'] ++;
18     }
19     for(i = 0; i < 26; i ++)
20     {
21         if(o[i] >= 100)
22         {
23             for(j = 0; j < 100; j ++)
24                 printf("%c",i+'a');
25             printf("
");
26             return 0;
27         }
28     }
29     for(i = 0; i < len; i ++)
30         s2[i] = s1[len-i-1];
31     for(i = 1; i <= len; i ++)
32     {
33         for(j = 1; j <= len; j ++)
34         {
35             if(s1[i-1] == s2[j-1])
36                 dp[i][j] = dp[i-1][j-1] + 1;
37             else
38                 dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
39         }
40     }
41     a = b = len;
42     num = 0;
43     while(a != 0&&b != 0)
44     {
45         if(s1[a-1] == s2[b-1])
46         {
47             que[num++] = s1[a-1];
48             a --;
49             b --;
50         }
51         else if(dp[a][b] == dp[a-1][b])
52             a --;
53         else if(dp[a][b] == dp[a][b-1])
54             b --;
55     }
56     if(num <= 100)
57     {
58         for(i = 0; i < num; i ++)
59         {
60             printf("%c",que[i]);
61         }
62     }
63     else
64     {
65         for(i = 0;i < 50;i ++)
66         {
67             printf("%c",que[i]);
68         }
69         for(i = 49;i >= 0;i --)
70         {
71             printf("%c",que[i]);
72         }
73     }
74     printf("
");
75     return 0;
76 }