【常规dp】P1415 拆分数列

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 
 7 const int maxn = 510;
 8 
 9 char s[maxn];
10 int f[maxn];
11 int t1[maxn], t2[maxn];
12 int dp[maxn];
13 
14 int cmp(int a, int b, int c, int d)
15 {
16     if (!d) return 1;
17     memset(t1, 0, sizeof(t1));
18     memset(t2, 0, sizeof(t2));
19     int cnt1, cnt2;
20     cnt1 = cnt2 = 0;
21     for (int i = b; i >= a; i--) t1[++cnt1] = s[i];
22     for (int i = d; i >= c; i--) t2[++cnt2] = s[i];
23     int len = max(cnt1, cnt2);
24     for (int i = len; i > 0; i--)
25     {
26         if (t1[i] != t2[i]) return t1[i] > t2[i];
27     }
28     return -1;
29 }
30 
31 int main()
32 {
33     scanf("%s", s + 1);
34     int len = strlen(s + 1);
35     for (int i = 1; i <= len; i++)
36     {
37         s[i] -= '0';
38     }
39     for (int i = 1; i <= len; i++)
40     {
41         f[i] = 1;
42         for (int j = i; j >= 1; j--)
43         {
44             if (cmp(j, i, f[j - 1], j - 1) == 1)
45             {
46                 f[i] = max(f[i], j);
47                 break;
48             }
49         }
50     }
51     dp[f[len]] = len;
52     int cnt = 0;
53     for (int i = f[len] - 1; i > 0 && !s[i]; i--)
54     {
55         dp[i] = len;
56         cnt++;
57     }
58     for (int i = f[len] - 1 - cnt; i >= 1; i--)
59     {
60         dp[i] = i;
61         for (int j = f[len] - 1; j >= i; j--)
62         {
63             if (!cmp(i, j, j + 1, dp[j + 1]))
64             {
65                 dp[i] = max(dp[i], j);
66                 break;
67             }
68         }
69     }
70     int pos = 1;
71     bool flag = true;
72     while (pos <= len)
73     {
74         if (flag) flag = false;
75         else cout << ',';
76         for (int i = pos; i <= dp[pos]; i++) cout << (int)s[i];
77         pos = dp[pos] + 1;
78     }
79 }