学步园

参照http://blog.csdn.net/a342374071/article/details/6689232

题目大意就是给定一些数字串，要你分别对每个数字串用逗号隔开，这样每个数字串中的数字保证是严格单调递增，且保证分隔后，最后的那个数字最小，当多种情况时要，那么取分隔后的第一个数字最大的，要是第一个数字也相同，那么看分隔后的第二个数字，如此下去，数字前面可以出现0，即000001表示1。

解题思考，两次动态规划。

第一次动态规划，保证最后的那个数字最小

dpforward[i]表示dpforward[i]~~~i这个段的数字串是上升子序列的一个数字；

dpforward[i] = max(dpforward[i], j+1),  其中dpforward[j]~j的数字串 小于 j+1 ~ i的数字串

对于全0的数字串要特殊处理，s1为全0，s2为全0，s1在s2的排列之前，那么s1 < s2，这样为了保重0能包括在子序列中

这样就能确定分隔后最后那个数字的宽度最小。

例如00010003对应的dpforward分别为0 1 2 3 3 3 3 4

dpforward[i]~~~i这个段的数字串是上升子序列的一个数字这段理解为，从后往前看，dp[7] = 4, 那么4 ~ dp[7]的数字为一个子串，

划分为0001,0003

确定了最后一个数字的最小宽度后，为了保证前几个数的第一，第二的序列最短，再进行一次反向的dp，从最后一个数字串前面一格往前进行dp

dpbackward[i] = max(dpbackward[i], j);  其中i~~j的数字串小于 j + 1~~~~dpbackward[j+1]的数字串

dpbackward[i]表示i~~~dpbackward[i]这个段的数字串是上升子序列的一个数字

最后根据dpbackward输出

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 90;

char s[maxn];
int len, dpforward[maxn], dpbackward[maxn];


bool cmp(int s1, int t1, int s2, int t2);

int main()
{
    while(true)
    {
        scanf("%s", s);
        len = strlen(s);
        if(len == 1 && s[0] == '0')
            break;
        memset(dpforward, 0, sizeof(dpforward));
        memset(dpbackward, 0, sizeof(dpbackward));
        for(int i = 1; i < len; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(cmp(dpforward[j], j, j+1, i))
                    dpforward[i] = max(dpforward[i], j+1);
            }
        }


        int tlen = dpforward[len-1];
        dpbackward[tlen]  = len - 1;
        for(int i = tlen - 1; s[i] == '0'; i--)
            dpbackward[i] = len - 1;
        for(int i = tlen - 1; i >= 0; i--)
        {
            for(int j = i; j <= tlen - 1; j++)
            {
                if(cmp(i, j, j + 1, dpbackward[j+1]))
                    dpbackward[i] = max(dpbackward[i], j);
            }
        }


        int pos = dpbackward[0], i = 0;
        while(i < len)
        {
            while(i <= pos && i < len)
                printf("%c", s[i++]);
            if(i < len)
                printf(",");
            pos = dpbackward[pos + 1];
        }
        printf("\n");
    }

    return 0;
}

bool cmp(int s1, int t1, int s2, int t2)
{
    while(s[s1] == '0' && s1 <= t1)
        s1++;
    while(s[s2] == '0' && s2 <= t2)
        s2++;
    if(s1 > t1 && s2 > t2)
        return true;

    if((t1 - s1) > (t2 - s2))
        return false;
    else if((t1 - s1) < (t2 - s2))
        return true;
    else
    {
        for(int i = s1, j = s2; i <= t1; i++, j++)
        {
            if(s[i] > s[j])
                return false;
            else if(s[i] < s[j])
                return true;
        }
    }
    return false;
}