题目大意：给一个数字串(不超过80位),可以在数字之间添加逗号，分成几个数，要求最后形成一个严格递增的序列，且要求最后一个数尽可能的小，如果有多个满足要求，则使第一个数尽可能大，如果还有多个，则使第二个最大，如此类推。求最后的序列。
先dp求出最后一个数最小可以是多少，然后反向dp求出在最后一个数最小情况下前面的数尽可能大，越前面优先级越高定义两个dp数组dp_min dp_max 第一个记录某个i点往后能延伸 的点序号即dp[i]-i就是末尾最小数的区间，dp_max则相反记录的是某个i之前的序列即i-dp[i]作为之前的最大数的区间。
#include <iostream> #include <cstdio> #include <cstring> #include <math.h> #include <algorithm> #include <queue> #include <map> using namespace std; typedef long long ll; const int N = 1000; const int mod=1e9+7; const double en=2.718281828459; using namespace std; #define inf (ll)1<<60 char ss[105]; int dp[105]; bool gtr(int i,int j,int u,int v){ int num1=j-i+1,num2=v-u+1; int l1=i,l2=u; while(ss[l1]=='0'&&l1<=j){ num1--; l1++; } while(ss[l2]=='0'&&l2<=j){ num2--; l2++; } //cout<<num1<<" "<<num2<<endl; if(num1>num2) return true; if(num1<num2) return false; if(num1==num2){ if(num1==0) return false; for(int i=0;i<num1;i++){ if(ss[l1+i]>ss[l2+i]) return true; if(ss[l1+i]<ss[l2+i]) return false; } return false; } } int main() { //freopen("in.txt","r",stdin); while(~scanf("%s",ss+1)){ //cout<<ss+1<<endl; int i,j; int l=strlen(ss+1); //cout<<l<<endl; //cout<<ss<<endl; if(l==1&&ss[1]=='0') break; dp[1]=1; // cout<<ss+1<<endl; for(i=2;i<=l;i++){ dp[i]=i; for(j=i;j>=1;j--){ if(gtr(j,i,j-dp[j-1],j-1)){ dp[i]=i-j+1; // cout<<i<<" "<<dp[i]<<endl; break; //cout<<i<<" "<<dp[i]<<endl; } } } int len=l-dp[l]+1; // cout<<len<<endl; dp[len]=dp[l]; for(i=len-1;i>=1;i--){ if(ss[i]=='0'){ dp[i]=dp[i+1]+1; continue; } for(j=len-1;j>=i;j--){ if(gtr(j+1,j+1+dp[j+1]-1,i,j)){ dp[i]=j-i+1; //cout<<i<<" "<<dp[i]<<" "<<j+1<<" "<<j+1+dp[j+1]-1<<endl; break; } } } //cout<<len<<endl; for(i=1;i<=l;i++){ //cout<<i<<" "<<dp[i]<<endl; for(j=i;j<=dp[i]+i-1;j++) printf("%c",ss[j]); j--; if(j!=l) printf(","); i=j; } printf(" "); } return 0; }