pku1239 Increasing Sequences (动态规划)

62 阅读 0 评论 41 点赞

我是靠谱客的博主瘦瘦棒棒糖，最近开发中收集的这篇文章主要介绍pku1239 Increasing Sequences (动态规划)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Increasing Sequences

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 1584		Accepted: 662

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

Sample Output

3,4,5,6

35,46

3,5,26

0001

100,000101



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

序列前面的数最大



分析：

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

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

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

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

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

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



#include
<iostream>
using namespace
std;
char
str[100];
int
dp[100], dp2[100], len;
int
compare(int
b1, int
e1, int
b2, int
e2)
//比较字符串str[b1...e1] 与字符串str[b2...e2]
{
while (str[b1]=='0')	b1++;
while (str[b2]=='0')	b2++;
int
len1 = e1-b1+1, len2 =e2-b2+1;
if (len1 != len2)
return
len1<len2 ? -1 : 1;
return
strncmp(str+b1, str+b2, len1);
}
int
main()
{
int
i, j, last;
while (cin>>str && (str[0]!='0' || str[1]!=0))
{
memset(dp, 0, sizeof(dp));
memset(dp2, 0, sizeof(dp2));
len = strlen(str);
//第一次DP
for (i=1; i<len; i++)
for (j=i-1; j>=0; j--)
{
//string[dp[j]..j] 与 string[j+1..i]的比较
if (compare(dp[j], j, j+1, i) < 0)
{
dp[i] = j+1;
break;
}
}
//初始化第二次DP, 加零等效
last = dp[len-1];
i = last;
dp2[i] = len-1;
while (str[i-1] == '0')
{
dp2[i-1] = len - 1;
--i;
}
//第二次DP
for (i=last-1; i>=0; i--)
for (j=i; j<last; j++)
{
//string[i..j] 与 string[j+1..dp2[j+1]]的比较
if (compare(i, j, j+1, dp2[j+1])<0 && dp2[i]<j)
{
dp2[i] = j;
}
}
i = 0;
char
s[100];
while (i<len)
{
strncpy(s, str+i, dp2[i]-i+1);
s[dp2[i]-i+1] = 0;
if (i != 0)
cout << ',';
cout << s;
i = dp2[i] + 1;
}
cout << endl;
}
}