说明

本题要求将一个数字字符串分割成严格递增的数字序列，且最后一个数字尽可能小。如果有多个解，选择字典序最大的序列。关键在于如何动态规划地找到最优分割点，确保序列严格递增且满足条件。

算法标签

• 动态规划：用于记录最优分割点
• 贪心算法：选择字典序最大的序列
• 字符串处理：比较数字字符串的大小

解题思路

1. 问题分析：

   • 需要将数字字符串分割成多个部分，每个部分转换为数字后严格递增。
   • 最后一个数字要尽可能小，且整体序列字典序最大。

2. 关键步骤：

   • 使用动态规划数组dp记录每个位置的最优分割点。
   • 从后向前遍历，确保最后一个数字最小。
   • 从前向后遍历，确保序列字典序最大。

3. 算法选择：

   • 动态规划预处理每个位置的最优分割点。
   • 贪心选择字典序最大的分割方式。

分析

1. 动态规划预处理：

   • dp[i]表示从位置i开始的最优分割点。
   • 从后向前填充dp数组，确保最后一个数字尽可能小。

2. 贪心构造序列：

   • 从前向后根据dp数组构造序列。
   • 每次选择当前最大的可能数字，确保严格递增。

3. 字符串比较：

   • 比较数字字符串时，先去除前导零，再按长度和字典序比较。

实现步骤

1. 输入处理：

   • 读取数字字符串，处理结束条件（输入为"0"）。

2. 动态规划填充：

   • 初始化dp数组。
   • 从后向前遍历，填充dp数组，确保最后一个数字最小。

3. 贪心构造序列：

   • 从前向后遍历，根据dp数组分割字符串。
   • 输出分割后的序列，用逗号分隔。

代码解释

• judge函数：比较两个数字字符串的大小，考虑前导零。
• 动态规划填充：从后向前确定每个位置的最优分割点。
• 贪心构造序列：从前向后分割字符串，确保字典序最大。
• 输出结果：按格式输出分割后的序列。

该方法通过动态规划和贪心算法高效地找到最优分割方案，确保序列严格递增且字典序最大。

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 88
#define nmax 6
char s[N];
int dp[N];
bool judge(int lx,int ly,int rx,int ry)
{
    while(s[lx]=='0') lx++;
    while(s[rx]=='0') rx++;
    int llen=ly-lx+1;
    int rlen=ry-rx+1;
    if(llen>rlen)
        return false;
    if(llen<rlen)
        return true;
    while(lx<=ly)
    {
        if(s[lx]<s[rx])
            return true;
        if(s[lx]>s[rx])
            return false;
        lx++;
        rx++;
    }
    return false;
}
int main()
{
    while(scanf("%s",s))
    {
        memset(dp,0,sizeof(dp));
        int len=strlen(s);
        if(len==1&&s[0]=='0')
            break;
        for(int i=1; i<len; i++)
        {
            for(int j=i-1; j>=0; j--) 
            {
  /*最后一个数的长度呈递增的顺序遍历（保证最后一个数尽可能小），
一定符合judge（）成立，即保存最后一个数的情况。
*/
                if(judge(dp[j],j,j+1,i))
                {
                    dp[i]=j+1;
                    break;
                }
            }
        }
        int last=dp[len-1]-1;  
        dp[last+1]=len-1;
//除了dp[len-1]对第二次dp有影响，前面dp的结果对后面dp的结果都没影响。
        for(int i=last; i>=0; i--)
        {//求从i开始，保证递增的情况下，dp[i]的值尽可能靠后（即尽可能大）
            if(s[i]=='0')
            {  //特殊情况，dp[i]的值直接为后面一个字符的dp[i+1]的值
                dp[i]=dp[i+1];
                continue;
            }
            for(int j=last+1; j>i; j--)
            {  //第一个数的最后一个字符的下标尽可能靠后
                if(judge(i,j-1,j,dp[j]))
                {
                    dp[i]=j-1;
                    break;
                }
            }
        }
        for(int i=0; i<=dp[0]; i++)
            printf("%c",s[i]);
        int k=dp[0]+1;
        while(k<len)
        {
            printf(",");
            for(int i=k; i<=dp[k]; i++)
                printf("%c",s[i]);
            k=dp[k]+1;
        }
        printf("\n");
    }
    return 0;
}