洛谷 P1464 Function 題解

記憶化搜尋，搜過的直接存起來避免重複搜尋

#include<stdio.h>
#define _for(i,j,k) for(int i=j;i<k;i++)
typedef long long ll;
int ans[21][21][21]={0};
int vis[21][21][21]={0};
int l[3]={1,1,1};
int w(int a,int b,int c)
{
	if (vis[a][b][c])
		return ans[a][b][c];
	else
	{
		int rslt;
		if (a<b&&b<c)
			rslt=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
		else
			rslt=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
		ans[a][b][c]=rslt;
		vis[a][b][c]=1;
		return rslt;
	}
}

int main()
{
	_for(i,0,21) _for(j,0,21) ans[0][i][j]=vis[0][i][j]=1;
	_for(i,0,21) _for(j,0,21) ans[i][0][j]=vis[i][0][j]=1;
	_for(i,0,21) _for(j,0,21) ans[i][j][0]=vis[i][j][0]=1;
	long long a,b,c;
	scanf("%lld%lld%lld",&a,&b,&c);
	while(a!=-1||b!=-1||c!=-1)
	{
		if (a<1||b<1||c<1)
			printf("w(%lld, %lld, %lld) = 1\n",a,b,c);
		else 
		{
			int aa=(int)a,bb=(int)b,cc=(int)c;
			if (a>20||b>20||c>20)
				aa=bb=cc=20;
			printf("w(%lld, %lld, %lld) = %d\n",a,b,c,w(aa,bb,cc));
		}
		scanf("%lld%lld%lld",&a,&b,&c);
	}
	return 0;
}