http://www.vijos.cn/Problem_Show.asp?id=1080
描述 Description
对于一个递归函数w(a,b,c)
如果a<=0 or b<=0 or c<=0就返回值1.
如果a>20 or b>20 or c>20就返回w(20,20,20)
如果a<b并且b<c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)
其它别的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)
这是个简单的递归函数，但实现起来可能会有些问题。当a,b,c均为15时，调用的次数将非常的多。你要想个办法才行.
输入格式 Input Format
会有若干行a,b,c,并以-1，-1，-1结束.
输出格式 Output Format
输出若干行
样例输入 Sample Input
1 1 1
2 2 2
-1 -1 -1
样例输出 Sample Output
w(1, 1, 1) = 2
w(2, 2, 2) = 4
来源 Source
Huyichen
分析：
此题不失为一道好的记忆化题目，对于每个产生过的都记录下来，对于后面访问用的就可以直接返回上一层，无需继续DFS下去。
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int F[22][22][22];
bool ok[22][22][22];
int a,b,c;
void Init()
{
memset(ok,false,sizeof(ok));
for (int i=0;i<=20;i++)
for (int j=0;j<=20;j++)
for (int k=0;k<=20;k++)
{
F[0][i][j]=1; ok[0][i][j]=true;
F[i][0][j]=1; ok[i][0][j]=true;
F[i][j][0]=1; ok[i][j][0]=true;
}
}
int dfs(int i,int j,int k)
{
if (ok[i][j][k]) return F[i][j][k];
if (i<j && j<k)
{
F[i][j][k]=dfs(i,j,k-1)+dfs(i,j-1,k-1)-dfs(i,j-1,k);
ok[i][j][k]=true;
return F[i][j][k];
}
F[i][j][k]=dfs(i-1,j,k)+dfs(i-1,j-1,k)+dfs(i-1,j,k-1)-dfs(i-1,j-1,k-1);
ok[i][j][k]=true;
return F[i][j][k];
}
int main()
{
Init();
while (scanf("%d%d%d",&a,&b,&c)!=EOF)
{
if (a==-1 && b==-1 && c==-1) break;
printf("w(%d, %d, %d) = ",a,b,c);
if (a<1 || b<1 || c<1)
{
printf("1\n");
continue;
}
if (a>20 || b>20 || c>20)
printf("%d\n",dfs(20,20,20));
else printf("%d\n",dfs(a,b,c));
}
return 0;
}