| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为了不重复计算...贴上代码//有点像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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator