hdoj比赛题.txt

北京大学 在线acm在线判题系统 一些题目解答

/*
   农夫三拳@seu
   drizzlecrj.gmail.com
   2007-03-02
*/
#include <iostream>
#include <cstring>

using namespace std;

long long w[21][21][21];

long long R(int a, int b, int c)
{
	if( a <= 0 || b <= 0 || c <= 0 )
		return w[0][0][0];
	else if( a > 20 || b > 20 || c > 20 )
	{
		if(w[20][20][20] == -1)
		{
			w[20][20][20] = R(20, 20, 20);
			return w[20][20][20];
		}
		else
		{
			return w[20][20][20];
		}
	}
	else if(a < b && b < c)
	{
		//w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
		if(w[a][b][c] == -1)
		{
			long long result = 0;
			if( w[a][b][c - 1] == -1 )
				result += R(a, b, c - 1);
			else
				result += w[a][b][c - 1];
			if(w[a][b - 1][c - 1] == -1)
				result += R(a, b - 1, c - 1);
			else
				result += w[a][b - 1][c - 1];
			if(w[a][b - 1][c] == -1)
				result -= R(a, b - 1, c);
			else
				result -= w[a][b - 1][c];
			w[a][b][c] = result;

			return result;
		}
		else
		{
			return w[a][b][c];
		}
	}
	else
	{
		if(w[a][b][c] == -1)
		{
			//w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
			long long result = 0;
			if( w[a - 1][b][c] == -1 )
				result += R(a - 1, b, c);
			else
				result += w[a - 1][b][c];
			if(w[a - 1][b - 1][c] == -1)
				result += R(a - 1, b - 1, c);
			else
				result += w[a - 1][b - 1][c];
			if(w[a - 1][b][c - 1] == -1)
				result += R(a - 1, b, c - 1);
			else
				result += w[a - 1][b][c - 1] ;
			if(w[a - 1][b - 1][c - 1] == -1)
				result -= R(a - 1, b - 1, c - 1);
			else
				result -= w[a - 1][b - 1][c - 1];

			w[a][b][c] = result;
			
			return result;
		}
		else
		{
			return w[a][b][c];
		}
	}
}

int main()
{
	int a, b, c;
	memset(w, -1, sizeof(w));
	w[0][0][0] = 1;
	//w[20][20][20] = 1048576;
	while( cin >> a >> b >> c && (a != -1 || b != -1 || c != -1) )
	{
		cout << "w(" << a << ", " << b << ", " << c << ") = "  << R(a, b, c) << endl;
	}

	return 0;
}