洛谷P1464 Function

记忆化搜索

思路
由于循环层数较多，暴力循环肯定超时，这里应采用记忆化搜索。
记忆化搜索
就是在搜索过程中可能同一组值得结果第一次就算出来了，第二次搜索就不要在去搜索这个以前就算出来的值，下一次搜到已经保存的值可以直接使用不用继续去搜索求值！可以大大减少搜索的深度和此数，这样就可以全部AC
AC code

#include<bits/stdc++.h>
using namespace std;
int s[100][100][100];
typedef long long ll;
ll a,b,c;
ll w(ll a,ll b,ll c)
{
	if(a<=0||b<=0||c<=0) return 1;
	if(a>20||b>20||c>20) return w(20,20,20);
	if(!s[a][b][c])
	{
		if(a<b&&b<c) s[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
		else s[a][b][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);
	
	}
	return s[a][b][c];
}
int main()
{
	while(1)
	{
		memset(s,0,sizeof s);
		cin>>a>>b>>c;
		if(a==-1&&b==-1&&c==-1) break;
		printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a,b,c));
	}
	return 0;
}

打赏