首页 > ACM题库 > HDU-杭电 > HDU 1511 Increasing Sequences-动态规划-[解题报告] C++
2013
12-12

HDU 1511 Increasing Sequences-动态规划-[解题报告] C++

Increasing Sequences

问题描述 :

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 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.

输出:

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.

样例输入:

3456
3546
3526
0001
100000101
0

样例输出:

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

非常经典的DP题!必须要好好研究!

需要两次dp,第一次dp正向,dp[i]的值x表示的是到了i,i前面的x个字符(包含i)组成数值后,前i个字符符合上升队列,且x为最大。则我们可以知道前i-dp[i]个也符合上升队列。

第一次dp求出符合题目要求的最后个数字的值为最小的值,注意这里说的是值而不是长度!因为对于如下测试数据

1234050

求出来符合要求的值是50,但是正确划分是

12,34,050

第二次dp为反向dp,求出符合题目要求的,第一个数字为最大的值,同时确定了这个值的长度!

第二次dp中的dp[i]的值为x,表示是到了i,i后面的x个字符(包含i)组成数字,i后面的所有字符符合上升队列,且x为最大。

第一次dp容易求,但是第二次dp因为数据中含有0,所以要分外小心,我就是在这里搞了很久,第二次一定要判断。

/*******************************************************************************
 # Author : Neo Fung
 # Email : [email protected]
 # Last modified: 2012-04-06 19:38
 # Filename: ZOJ1499 POJ1239 HDU1511 Increasing Sequences.cpp
 # Description : 
 ******************************************************************************/
#ifdef _MSC_VER
#define DEBUG
#define _CRT_SECURE_NO_DEPRECATE
#endif

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
#define MAX 100
using namespace std;

char num[MAX];
int dp[MAX],dprev[MAX];
int now[MAX],ans[MAX];

bool check( char *lhs,int n, char *rhs,int m)
{
	char *p=lhs,*q=rhs;
	while(*p=='0' && n)
	{
		++p;
		--n;
	}
	while(*q=='0' && m)
	{
		++q;
		--m;
	}
	if(n<m)
		return true;
	else if(n>m)
		return false;
	for(int i=0;i<n;++i)
		if(*p<*q)
			return true;
		else if(*p>*q)
			return false;
		else
		{
			++p;
			++q;
		}
	return false;
}

int main(void)
{
#ifdef DEBUG  
  freopen("../stdin.txt","r",stdin);
  freopen("../stdout.txt","w",stdout); 
#endif  

  int ncase=1;
  //   scanf("%d",&ncase);

	while(gets(num+1))
  {
		int n=strlen(num+1)+1;
		if(n==2 && num[1]=='0')
			break;

		num[0]='0';
		memset(dp,0,sizeof(dp));
		memset(now,0,sizeof(now));
		dp[1]=1;
		
		for(int i=2;i<n;++i)
		{
			dp[i]=i;
			for(int j=i-1;j>0;--j)
			{
				int t=i-j;
				if(check(num+j-dp[j]+1,dp[j],num+j+1,t))
				{
					dp[i]=t;
					break;
				}
			}
		}
		int pos=n-1;
		while(pos>0)
		{
			now[pos-dp[pos]+1]=dp[pos];
			pos=pos-dp[pos];
		}

    int last=n-dp[n-1];
		dp[last]=dp[n-1];

		for(int i=last-1;i>0;--i)
		{
			dp[i]=-1;
      if(num[i]=='0')  
      {  
        dp[i]=dp[i+1]+1;  
        continue;  
      }  
			for(int j=last;j>i;--j)
				if(check(num+i,j-i,num+j,dp[j]))
				{
					dp[i]=j-i;
					break;
				}
		}

		pos=1;
		memset(ans,0,sizeof(ans));
		while(pos<n)
		{
			ans[pos]=1;
			pos=pos+dp[pos];
		}

		for(int i=1;i<n;++i)
		{
			if(ans[i]&&i>1)
				printf(",");
			printf("%c",num[i]);
		}
		printf("\n");
	}
	return 0;

}

解题报告转自:http://blog.csdn.net/neofung/article/details/7433493


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。