DP
数列长度过大无法枚举，考虑DP
设f1[i]储存以第i个字符为结尾时，的最后一个数最小时，这个数的开头的位置
（很难想有木有）
OK,状态有了，方程想一想就出来了：
设$num[i][j]$为数列中从i到j的数连起来后的值,$len$为数列长度
则
如果$num[ j ][ i ]>num[ f1[ j -1 ] ][ j-1 ]$（ $j$从$i$到1 ,$1<=i<=len$）则$f1[ i ]$等于$j$,并且直接退出当前循环
因为$j$从后往前枚举，所以一旦找到符合的j就是$num[ f1[ i ] ][ i ]$的最小值
至于$num$的判断只要打个暴力循环就好了..数据太小..
然后是输出字典序最小的答案(划重点)
仍然是DP..
设$f2[i]$存储以第i个字符为开头时，的最后一个数最小时，这个数的结尾的位置（貌似只是倒过来了..）
同样如果$num[i][j]<num[j+1][f2[j+1]]$（ $j$从$n$到$i$,$i$从$n$到$1$）则$f2[i]$等于$j$,并且直接退出当前循环.
还有$f2[f[len]]$初始为$len$
有一点要注意最后一个数可以有前导0..
"如果第一次dp计算出最小末尾为50，但输入是……00050。
这样上面的转移方程不会将000和50分成一组，因为I≤j≤f[n] 。
这样000所在状态就和状态定义不符，它没表示出最大末尾。"
__by Rapiz
所以要先把最后一个数的前导0单独处理
听同机房的dalao说好像数据可以扩10倍，判断的话就要用神奇的后缀数组什么的..我也不清楚唉
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; char s[507]; int n,f1[507],f2[507]; inline bool pd(int la,int ra,int lb,int rb)//暴力的判断函数 { while(s[la]==0&&la<ra) la++; while(s[lb]==0&&lb<rb) lb++; //cout<<la<<" "<<ra<<" "<<lb<<" "<<rb<<endl; if(ra-la!=rb-lb) { if(ra-la>rb-lb) return 1; else return 0; } int len=ra-la; //cout<<len<<endl; //printf("%d %d",s[la+0],s[lb+0]); //cout<<endl; for(int i=0;i<=len;i++) if(s[la+i]!=s[lb+i]) return s[la+i]>s[lb+i]; return 0; } int main() { scanf("%s",s+1); for(int i=1;s[i];i++,n++) s[i]-='0'; //DP开始 for(int i=1;i<=n;i++) { for(int j=i;j>0;j--) if(pd(j,i,f1[j-1],j-1)) { f1[i]=j; break; } } int tot=1; //cout<<f1[n]; for(int i=f1[n]-1;i&&s[i]==0;i--) f2[i]=n,tot++; f2[f1[n]]=n; for(int i=f1[n]-tot;i>0;i--) { f2[i]=i; for(int j=f1[n]-1;j>=i;j--) if(pd(j+1,f2[j+1],i,j)) { f2[i]=max(f2[i],j); break; } } int pos=f2[1]; for(int i=1;i<=n;i++) { if(i==pos&&i!=n) { printf("%d,",s[i]); pos=f2[i+1]; continue; } printf("%d",s[i]); } return 0; }