洛谷1415 拆分数列

题意

给出一个数字串，要求用逗号将其分成若干个严格递增的数。如果有多解要求最后一个数最小，如果还有多解要求字典序最大。

数字串长度 $\le 500$ 。

题解

先正着推出最后一个最小的数。用 $f[i]$ 代表以 $i$ 结尾的数的最近的开头，可以逆序枚举 $j$ ，如果 $[f[j-1],j-1] < [j,i]$ ，那么 $f[i]=j$ 。

然后反着推一个最大的数。用 $g[i]$ 表示以 $i$ 为开头的数的最远的结尾，方程式同理。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=505;
char s[N];
int n,f[N],g[N];

inline bool cmp(int l1,int r1,int l2,int r2) //检验 [l1,r1] 是否 < [l2,r2]
{
    for (;l1<=r1 && !s[l1];l1++);
    for (;l2<=r2 && !s[l2];l2++);
    if (l1>r1 || l2>r2) return 0;
    int L1=r1-l1+1,L2=r2-l2+1;
    if (L1^L2) return L1<L2;
    for (;l1<=r1;l1++,l2++) if (s[l1]^s[l2]) return s[l1]<s[l2];
    return 0;
}

signed main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for (int i=1;i<=n;i++) s[i]^=48;
    for (int i=1;i<=n;i++)
    {
        f[i]=1;
        for (int j=i;j;j--)
        {
            if (!cmp(f[j-1],j-1,j,i)) continue;
            f[i]=j;
            break;
        }
    }
    for (int i=f[g[f[n]]=n];!s[i-1];i--) g[i-1]=n; //0可以全部算到最后一个
    for (int i=f[n]-1;i;i--)
    {
        for (int j=f[n]-1;j>=i;j--)
        {
            if (!cmp(i,j,j+1,g[j+1])) continue;
            g[i]=j;
            break;
        }
    }
    for (int i=1;i<=n;i=g[i]+1)
    {
        if (i>1) printf(",");
        for (int j=i;j<=g[i];j++) printf("%d",s[j]);
    }
    return 0;
}