题目传送门
两次DP
Description
Given a string of digits, insert commas to create a sequence of strictly increasing numbers so as to minimize the magnitude of the last number. For this problem, leading zeros are allowed in front of a number.
Input
Input will consist of multiple test cases. Each case will consist of one line, containing a string of digits of maximum length 80. A line consisting of a single 0 terminates input.
Output
For each instance, output the comma separated strictly increasing sequence, with no spaces between commas or numbers. If there are several such sequences, pick the one which has the largest first value;if there’s a tie, the largest second number, etc.
Sample Input
3456
3546
3526
0001
100000101
0
Sample Output
3,4,5,6
35,46
3,5,26
0001
100,000101
题意：
给出一串序列，现在要添加逗号作为分隔符，使得序列是递增序列，然后让最后一个数尽量小，第一个数尽量大
分析：
解题思考，两次动态规划。
第一次动态规划，保证最后的那个数字最小
dpforward[i]表示dpforward[i] -> i这个段的数字串是上升子序列的一个数字；
dpforward[i] = max(dpforward[i], j+1), 其中dpforward[j]~j的数字串 小于 j+1 -> i的数字串
对于全0的数字串要特殊处理，s1为全0，s2为全0，s1在s2的排列之前，那么s1 < s2，这样为了保重0能包括在子序列中
这样就能确定分隔后最后那个数字的宽度最小。
例如00010003对应的dpforward分别为0 1 2 3 3 3 3 4
dpforward[i] -> i这个段的数字串是上升子序列的一个数字这段理解为，从后往前看，dp[7] = 4, 那么4 -> dp[7]的数字为一个子串，
划分为0001,0003
确定了最后一个数字的最小宽度后，为了保证前几个数的第一，第二的序列最短，再进行一次反向的dp，从最后一个数字串前面一格往前进行dp
dpbackward[i] = max(dpbackward[i], j); 其中i -> j的数字串小于 j + 1 -> dpbackward[j+1]的数字串
dpbackward[i]表示i -> dpbackward[i]这个段的数字串是上升子序列的一个数字
最后根据dpbackward输出
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = 80 + 5;int d[maxn];
char s[maxn];bool judge(int i, int j, int x, int y) //判断【i，j】是否大于【x，y】
{
int len1=j-i+1;int len2=y-x+1;while(s[i]=='0') {
i++;len1--;}while(s[x]=='0') {
x++;len2--;}if(len1>len2) return true;else if(len1<len2) return false;else{
for(int k=0; k<len1;k++){
if(s[k+i]>s[x+k]) return true;else if(s[k+i]<s[x+k]) return false;}}return false;
}int main()
{
//freopen("in.txt","r",stdin);while(~scanf("%s",s+1)){
int n=strlen(s+1);if(n==1 && s[1]=='0') break;//从头到尾找最小长度for(int i=1;i<=n;i++){
d[i]=i;for(int j=i-1;j>=1;j--){
if(judge(j+1,i,j-d[j]+1,j)){
d[i]=i-j;break;}}}//从尾到头找最大长度int t=n-d[n]+1; //[t,n]已经是决定了的，不能改变d[t]=d[n];for(int i=n-d[n];i>=1;i--){
if(s[i]=='0'){
d[i]=d[i+1]+1;continue;}for(int j=t;j>i;j--){
if(judge(j,j+d[j]-1,i,j-1)){
d[i]=j-i;break;}}}int tmp=d[1]+1;for(int i=1;i<=n;i++){
if(tmp==i){
printf(",");tmp=d[i]+i;}printf("%c",s[i]);}printf("\n");}return 0;
}