POJ 题目1239 ||ZOJ 题目 1499 Increasing Sequences（正反两次DP）

Description

Input

Output

Sample Input

3456
3546
3526
0001
100000101
0  

Sample Output

3,4,5,6
35,46
3,5,26
0001
100,000101  

Source

East Central North America 2002

思路：http://blog.csdn.net/vecri/article/details/4758786

题目大意： 给定一个字符串， 如3456, 将其分割成多个整数，使该整数序列递增，且尽可能使最大的数也就是序列最后一个数最小，在这个前提下使


序列前面的数最大





分析：


两次DP, 一次前向DP，一次后向DP


第一次DP来确定最后一个数字，因为这个数字是递增序列的最后一个数，且这个数必须最小,


代码中dp[i]=j是指由str[1...i]序列生成的递增序列的最后一个数是str[j...i]


第二次DP是在确定最后一个数字的基础上，往前规划，使得前面的数尽可能的大，


代码中dp2[i]=j是指在确定最后一个数的情况下，str[i...end]序列中最大的开头数为str[i...j]


注意最后一个数前面可以加零。

  

ac代码

#include<stdio.h>
#include<string.h>
char str[110],s[110];
int dp[110],dp2[110];
int cmp(int b1,int e1,int b2,int e2)
{
	while(str[b1]=='0')
		b1++;
	while(str[b2]=='0')
		b2++;
	int len1=e1-b1+1;
	int len2=e2-b2+1;
	if(len1<len2)
		return -1;
	else
		if(len1>len2)
			return 1;
		else
			return strncmp(str+b1,str+b2,len1);
}
int main()
{
	while(scanf("%s",str)!=EOF)
	{
		if(strcmp(str,"0")==0)
			break;
		memset(dp,0,sizeof(dp));
		memset(dp2,0,sizeof(dp2));
		int len=strlen(str);
		int i,j;
		for(i=1;i<len;i++)
		{
			for(j=i-1;j>=0;j--)
			{
				if(cmp(dp[j],j,j+1,i)<0)
				{
					dp[i]=j+1;
					break;
				}
			}
		}
		i=dp[len-1];
		dp2[i]=len-1;
		while(str[i-1]=='0')
		{
			dp2[i-1]=len-1;
			--i;
		}
		for(i=dp[len-1]-1;i>=0;i--)
		{
			for(j=i;j<dp[len-1];j++)
			{
				if(cmp(i,j,j+1,dp2[j+1])<0&& dp2[i]<j)
				{
					dp2[i]=j;
				}
			}
		}
		i=0;
		while(i<len)
		{
			strncpy(s,str+i,dp2[i]-i+1);
			s[dp2[i]-i+1]='\0';
			if(i!=0)
				printf(",");
			printf("%s",s);
			i=dp2[i]+1;
		}
		printf("\n");
	}
}