游客 注册 | 登录
中文 | En

1787 - 递增序列

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

给定一个数字串，请你插入若干个逗号，使得该数字串成为一个严格递增的数列且最后一个数要尽可能小，在这个问题中，前导的零是允许出现在数的前面的。

题目输入

输入数据仅含一行，为一个长度不超过80的数字串。

题目输出

输出一个严格递增且最后一数最小的数列，相邻两个数之间用一个逗号隔开，如果有多个数列满足要求，则输出第一个数最大的那个数列，若这样的解还不止一个，则输出第二个数最大的那个数列，以此类推。

输入/输出样例

输入格式

100000101

输出格式

100,000101

C++解答

#include <cstdio>
#include <cstring>
using namespace std;
const int N(83);
int a[N]={0},f[N]={0},num[N][N]={0},last,end;
bool flag[N]={0};
void init()
{
    char *s=new(char);
    scanf("%s",s);
    for(int i=0;s[i];i++) a[i+1]=s[i]-'0',a[0]=i+1;
    for(int i=1;i<=a[0];i++)
        for(int j=i;j<=a[0];j++)
            num[i][j]=num[i][j-1]*10+a[j];
}
void solve()
{
    f[0]=-1;
    for(int i=2;i<=a[0];i++)
        for(int j=i-1;j>=0;j--)
            if(num[j+1][i]>num[f[j]+1][j])
            {
                f[i]=j;
                break;
            }
    last=num[f[a[0]]+1][a[0]];
    end=f[a[0]];
    
    memset(f,0,sizeof(f));
    f[0]=-1;
    for(int i=2;i<=end;i++)
        for(int j=0;j<i;j++)
            if(num[f[j]+1][j]<num[j+1][i]&&num[j+1][i]<last)
            {
                f[i]=j;
                break;
            }
    int x=end;
    while(x)
    {
        flag[x]=true;
        x=f[x];
    }
}
void print()
{
    for(int i=1;i<=a[0];i++)
    {
        printf("%d",a[i]);
        if(flag[i])
            printf(",");
    }
    printf("\n");
}
int main()
{
    init();
    solve();
    print();
    return 0;
}
请先登陆