题目描述
给出一列数字，需要你添加任意多个逗号将其拆成若干个严格递增的数。如果有多组解，则输出使得最后一个数最小的同时，字典序最大的解（即先要满足最后一个数最小；如果有多组解，则使得第一个数尽量大；如果仍有多组解，则使得第二个数尽量大，依次类推……）。
输入输出格式
输入格式：
共一行，为初始的数字。
输出格式：
共一行，为拆分之后的数列。每个数之间用逗号分隔。行尾无逗号。
输入输出样例
[1] 3456 [2] 3546 [3] 3526 [4] 0001 [5] 100000101
[1] 3,4,5,6 [2] 35,46 [3] 3,5,26 [4] 0001 [5] 100,000101
【数据范围】
对于10%的数据，输入长度<=5
对于30%的数据，输入长度<=15
对于50%的数据，输入长度<=50
对于100%的数据，输入长度<=500
题解
- 首先，我们可以dp求出为以i结尾的最小结尾数的起始坐标d[i]
- 求这个dp时，要枚举起始坐标j
- 那何为满足条件？
- 也就是结尾数要大于[d[j-1],j-1]
- 那么最小的话，就是找到一个就直接break，因为这个数是倒过来找的
- 然后我们还要跑一个dp，从i开始的序列的第一个数的最后的坐标f[i]
- 题目上说，要满足最后一个数最小，那么我们在上一个dp里求出来的最后一个数，就是答案的最后一个数
- 求这个的话，从后往前找
- 也向上面一样，要满足题目的要求
- 最后，pos沿着f数组找就可以找到全部数
代码
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 int d[505],f[505],n,a[505]; 6 char s[505]; 7 bool pd(int l1,int r1,int l2,int r2) 8 { 9 while (l1<=r1&&a[l1]==0) l1++; 10 while (l2<=r2&&a[l2]==0) l2++; 11 if (r1-l1+1==0||r2-l2+1==0) return false; 12 if (r1-l1+1<r2-l2+1) return true; 13 if (r1-l1+1>r2-l2+1) return false; 14 int len=r1-l1+1; 15 for (int i=0;i<len;i++) 16 { 17 if (a[l1+i]<a[l2+i]) return true; 18 if (a[l1+i]>a[l2+i]) return false; 19 } 20 return false; 21 } 22 void dp1() 23 { 24 for (int i=1;i<=n;i++) 25 { 26 d[i]=1; 27 for (int j=i;j>=1;j--) 28 if (pd(d[j-1],j-1,j,i)) 29 { 30 d[i]=j; 31 break; 32 } 33 } 34 } 35 void dp2() 36 { 37 f[d[n]]=n; 38 int x=d[n]; 39 while (a[x-1]==0) f[x-1]=n,x--; 40 for (int i=d[n]-1;i>=1;i--) 41 for (int j=d[n]-1;j>=i;j--) 42 if (pd(i,j,j+1,f[j+1])) 43 { 44 f[i]=j; 45 break; 46 } 47 } 48 int main() 49 { 50 scanf("%s",s+1); 51 n=strlen(s+1); 52 for (int i=1;i<=n;i++) a[i]=s[i]-'0'; 53 dp1(); dp2(); 54 int pos=1; 55 while (pos<=n) 56 { 57 if (pos!=1) putchar(','); 58 for (int i=pos;i<=f[pos];i++) printf("%d",a[i]); 59 pos=f[pos]+1; 60 } 61 return 0; 62 }