作者Lyh注：本题解法并不优


        记录一道费一天时间才A的一道省选难度题

难度：省选/NOI-

题目描述

        给出一列数字，需要你添加任意多个逗号将其拆成若干个严格递增的数。如果有多组解，则输出使得最后一个数最小的同时，字典序最大的解（即先要满足最后一个数最小；如果有多组解，则使得第一个数尽量大；如果仍有多组解，则使得第二个数尽量大，依次类推……）。

【数据范围】
        对于10%的数据，输入长度≤5
        对于30%的数据，输入长度≤15
        对于50%的数据，输入长度≤50
        对于100%的数据，输入长度≤500

输入输出格式

输入格式：

        共一行，为初始的数字。

输出格式：

        共一行，为拆分之后的数列。每个数之间用逗号分隔。行尾无逗号。

输入输出样例

Sample input

[1]
3456
[2]
3546
[3]
3526
[4]
0001
[5]
100000101

Sample output

[1]
3,4,5,6
[2]
35,46
[3]
3,5,26
[4]
0001
[5]
100,000101

题解

        本题还是有难度的，考察动态规划上的字符串问题。答案字典序最大和末尾数最小限制是坑点。
        第一步，找到末尾最小的那个数。若记dp1(i，r)表示第i个元素前已经加了逗号，是否在区间[0,i-1]存在一种加逗号方案使得它们严格递增且小于[i,r]表示的数。若有值为1，否则为0。这样便有状态转移方程：(区间表示的数的关系暂且记作区间的关系)

        注意dp1(0，r)=1(也就是true)恒成立。由此可以得到使得dp1(k，length-1)(length为字符串长度)为1的最大的k，[k,length-1]一定为右侧最小的数。这里记这个k为key。
        值得注意的是，如果key前方有0，那么将key左移几个单位末尾数的最小值是不变的。这警示我们不能直接就在key处加一个逗号，还需要考虑前导0的问题。可以搜索出key前方最后一个0出现的位置，把它记作key2。这时如果key2=0，那么一个逗号都不用加，直接输出即可(因为此时末尾数最小，最开始的数为序列的全部，一定是最大的，符合题意)。否则进入下一步。
        下面探讨key2 > 0的情景。由于序列要求是字典序最大的一个，可以定义dp2(i，l)表示第i个元素后已经加了一个逗号，在[i+1,p]是否有一种加逗号方案使得它们严格递增且都大于[l,i]所表示的数。若有dp2(i，l)为从i开始的逗号最右位置序号，否则为-1。注意这里的p表示[key2-1,key-1]中的任意整数值。
        于是有状态转移方程：

        在key2-1≤i≤key-1时，只要满足[l,i]<[key,length-1]，之后就不需要加任何逗号（只需加i后面那一个即可），它的dp2值即为i，如果不满足则为-1。
        根据方程递推，在适当的地方加逗号即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include <cstring>

#define MAX 500
#define inf (int)1e8
using namespace std;
string op;
int dp[MAX][MAX], key, dp2[MAX][MAX], key2;

inline bool check(int a, int b, int c, int d) {//s1<s2?
    while (op[a] == '0')a++;//去前导0
    while (op[c] == '0')c++;
    if (b - a > d - c)return false;
    if (b - a < d - c)return true;
    for (; a <= b && c <= d; a++, c++) {
        if (op[a] < op[c])return true;
        if (op[a] > op[c])return false;
    }
    return false;
}

int DP(int poi, int r) {
    if (dp[poi][r] < inf)return dp[poi][r];
    if (poi == 0)return 1;
    for (int i = poi - 1; i >= 0; i--) {
        if (check(i, poi - 1, poi, r)) {
            if (DP(i, poi - 1) != 0)return dp[poi][r] = 1;
        }
    }
    return dp[poi][r] = 0;
}

int DP2(int x, int l) {
    if (dp2[x][l] < inf)return dp2[x][l];
    if (key2 - 1 <= x && x < key) {
        if (check(l, x, key, op.length() - 1))return x;
        return dp2[x][l] = -1;
    }
    for (int i = key - 1; i > x; i--) {
        if (check(l, x, x + 1, i)) {
            if (DP2(i, x + 1) != -1)return dp2[x][l] = i;
        }
    }
    return dp2[x][l] = -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> op;
    string ans = op;
    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAX; j++)dp[i][j] = dp2[i][j] = inf;
    for (int i = op.length() - 1; i >= 0; i--)
        if (DP(i, op.length() - 1) == 1) {
            key = i;
            break;
        }
    for (int i = key - 1; i >= 0; i--)
        if (op[i] != '0') {
            key2 = i + 1;
            break;
        }
    if (key == 0 || key2 == 0) {//不加任何逗号，直接输出
        cout << op;
        return 0;
    }
    int l = 0, r = key - 1, ch = 0;//ch为偏移量
    while (true) {//至少加两个逗号
        int t = DP2(r, l);
        if (key2 - 1 <= t && t < key) {
            ans.insert(r + 1 + ch, ",");
            if (r != t)ans.insert(t + 1 + ch + 1, ",");//防止多加逗号
            break;
        } else if (t == -1)r--;
        else ans.insert(r + 1 + ch, ","), l = r + 1, r = t, ch++;
    }
    cout << ans << endl;
    return 0;
}