Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为了不重复计算...贴上代码

Posted by kaitian5201314 at 2010-08-23 17:25:17 on Problem 1579
//有点像DP的备忘录...0ms AC... 
//存在巨大的时间浪费,主要是很多已经计算好的值又要被重新计算
//就像递归求Fibonacci数列一样,很多子递归进行很多次
//所以运用备忘录的形式,把已经计算好的数据放在数组里,递归之前先检查是否已经算好了
//算好了的话直接拿来用就行了

#include<iostream>
using namespace std;

int visit[21][21][21];

int r(int a,int b,int c)
{
	

	if(a<=0||b<=0||c<=0)//注意啦...这个必须放前面...想象为什么吧
		return visit[a][b][c]=1;

	

	if(a>20||b>20||c>20)
		return r(20,20,20);

	if(visit[a][b][c])
		return visit[a][b][c];

	if(a<b&&b<c)
	{
		return visit[a][b][c]=r(a, b, c-1) + r(a, b-1, c-1) - r(a, b-1, c);
	}

	return visit[a][b][c]=r(a-1, b, c)+r(a-1, b-1, c)+r(a-1, b, c-1)-r(a-1, b-1, c-1);
	

}
int main()
{
	//freopen("1.txt","r",stdin);

	int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c))
	{
		memset(visit,0,sizeof(visit));

		if(a==-1&&b==-1&&c==-1)
			return 0;

		printf("w(%d, %d, %d) = %d\n",a,b,c,r(a,b,c));
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator