首页 > ACM题库 > HDU-杭电 > HDU 1502 Regular Words-动态规划-[解题报告] C++
2013
12-11

HDU 1502 Regular Words-动态规划-[解题报告] C++

Regular Words

问题描述 :

Consider words of length 3n over alphabet {A, B, C} . Denote the number of occurences of A in a word a as A(a) , analogously let the number of occurences of B be denoted as B(a), and the number of occurenced of C as C(a) .

Let us call the word w regular if the following conditions are satisfied:

A(w)=B(w)=C(w) ;
if c is a prefix of w , then A(c)>= B(c) >= C(c) .
For example, if n = 2 there are 5 regular words: AABBCC , AABCBC , ABABCC , ABACBC and ABCABC .

Regular words in some sense generalize regular brackets sequences (if we consider two-letter alphabet and put similar conditions on regular words, they represent regular brackets sequences).

Given n , find the number of regular words.

输入:

There are mutiple cases in the input file.

Each case contains n (0 <= n <= 60 ).

There is an empty line after each case.

输出:

Output the number of regular words of length 3n .

There should be am empty line after each case.

样例输入:

2

3

样例输出:

5

42

解题:设函数dp[i][j][k]表示该序列中有i个A,j个B,k个C组成,则dp[i][j][k]是有dp[i-1][j][k],dp[i][j-1][k],dp[i][j][k-1]这三个添加过来的,所以动态转移方程式

dp[i][j][k]=dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1];同时注意,dp的结果很大,要用到大数。

设sum[i]表示当n为i时的结果,即当i==j==k时的结果。(注意:把dp和sum都定义成char型数组,否则会超存)。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#define N 80
using namespace std;

char num[62][N],dp[62][62][62][N];

void sum(char a[N],char b[N])
{
	int n=a[0],m=b[0],i,j,k;
	a[0]=k=max(n,m);	
	for(i=1;i<=k;i++)
	{
		a[i]+=b[i];
		if(a[i]>9)
		{
			a[i+1]++;			a[i]%=10;
			if(i+1>k)
			{
				k++;a[0]++;
			}
		}
	}
}
void cpy(char a[N],char b[N])
{
	int i;
	for(i=0;i<=b[0];i++)
	{
		a[i]=b[i];
	}
}
void add(int x,int y,int z)
{
	if(x-1>=0&&x-1>=y&&y>=z)
		sum(dp[x][y][z],dp[x-1][y][z]);
	if(y-1>=0&&x>=y-1&&y-1>=z)
		sum(dp[x][y][z],dp[x][y-1][z]);
	if(z-1>=0&&x>=y&&y>=z-1)
		sum(dp[x][y][z],dp[x][y][z-1]);
}
void fun()
{
	int i,j,k;
	memset(dp,0,sizeof(dp));
	dp[0][0][0][0]=dp[0][0][0][1]=1;
	for(i=1;i<=60;i++)
		for(j=0;j<=i;j++)
			for(k=0;k<=j;k++)
			{
				add(i,j,k);
				if(i==j&&j==k)
				{
					cpy(num[i],dp[i][j][k]);
				}
			}
}
int main()
{
	fun();
	int n;
	while(~scanf("%d",&n))
	{
		for(int i=num[n][0];i>0;i--)
			printf("%d",num[n][i]);
		printf("\n\n");
	}
}

解题报告转自:http://blog.csdn.net/jiang199235jiangjj/article/details/7452389


  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮