拆分数列

题目背景

【为了响应党中央勤节俭、反铺张的精神，题目背景描述故事部分略去】

题目描述

给出一列数字，需要你添加任意多个逗号将其拆成若干个严格递增的数。

如果有多组解，则输出使得最后一个数最小的同时，字典序最大的解（即先要满足最后一个数最小；如果有多组解，则使得第一个数尽量大；如果仍有多组解，则使得第二个数尽量大，依次类推……）。

输入输出格式

输入格式：

共一行，为初始的数字。

输出格式：

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

数据范围

对于$10\%$的数据，输入长度$\le5$

对于$30\%$的数据，输入长度$\le15$

对于$50\%$的数据，输入长度$\le50$

对于$100\%$的数据，输入长度$\le500$

这个题还挺巧妙的。

发现要求是字典序构造，而且两组要求看起来不太一样。

考虑分开做，先在保证有解的情况下找到最后一个最小的数。

令$dp_i$代表以$i$为结束时的字符串的最大前缀位置（即满足最后一位最小），这样我们每次找的都是最小的位，具有最优子结构性质。

转移：

$$dp_i=max_{num_{j,i}>num_{dp_{j-1},j-1},j\le i} \ j$$

$num_{i,j}$代表从$i$到$j$的数字大小

注意比较的复杂度，所以总体是$O(n^3)$的，不过上界非常松

然后我们再反着做一遍类似的$DP$，发现还是由最大前缀推了最大前缀的，所以刚好满足了要求$2$

注意前导$0$的一些特判

Code:

#include <cstdio>

#include <cstring>

const int N=502;

int n,dp[N];

char s[N];

bool check(int l1,int r1,int l2,int r2)//前是否大于后

{

    if(r2==0) return 1;

    while(s[l1]=='0'&&l1<=r1) ++l1;

    while(s[l2]=='0'&&l2<=r2) ++l2;

    if(r1-l1>r2-l2) return 1;

    else if(r1-l1<r2-l2) return 0;

    while(l1<=r1&&l2<=r2&&s[l1]==s[l2]) ++l1,++l2;

    return s[l1]>s[l2];

}

int main()

{

    scanf("%s",s+1);

    n=strlen(s+1);

    for(int i=1;i<=n;i++)

        for(int j=i;j;j--)

            if(check(j,i,dp[j-1],j-1))

            {

                dp[i]=j;

                break;

            }

    int d=dp[n],pos=dp[n];

    memset(dp,0,sizeof(dp));

    dp[pos]=n;

    while(s[pos-1]=='0') --pos,dp[pos]=n;

    for(int i=pos-1;i;i--)

        for(int j=d;j>=i;j--)

            if(check(j+1,dp[j+1],i,j))

            {

                dp[i]=j;

                break;

            }

    for(int l=1,r;l<=n;l=r+1)

    {

        r=dp[l];

        for(int j=l;j<=r;j++) printf("%c",s[j]);

        if(r!=n) printf(",");

    }

    return 0;

}

2018.10.21

拆分

洛谷 P1415 拆分数列 解题报告