我用的是memorized search，老是超时，问问牛人DP怎么过的？

#include <stdio.h>

#include <algorithm>

#include <memory.h>

#include <string.h>

#include  <vector>

using namespace std;


const int MAX_N = 12;

typedef struct state
{
	int stones[MAX_N];
	int count;
}State;

vector<State> cachedState;
vector<bool> cachedResult;

bool Failure (State s)
{
	int i = 0;
	for (i = 0; i < s.count; ++i)
	{
		if (s.stones[i] >= 2)
		{
			return false;
		}
	}

	return true;
}

bool SameState (State& s1, State s2)
{
	int hash[101] = {0};
	
	int i = 0;
	for (i = 0; i < s1.count; ++i)
	{
		hash[s1.stones[i]]++;
	}

	for (i = 0; i < s2.count; ++i)
	{
		hash[s2.stones[i]]--;
	}

	for (i = 0; i < s1.count; ++i)
	{
		if (hash[i] != 0)
		{
			return false;
		}
	}

	return true;
}

bool Solve (State s)
{
	if (Failure(s))
	{
		cachedState.push_back(s);
		cachedResult.push_back(false);
		return false;
	}

	int i = 0;
	int j = 0;
	int k = 0;
	int t = 0;

	for (i = 0; i < cachedState.size(); ++i)
	{
		if (SameState(s, cachedState[i]))
		{
			return cachedResult[i];
		}
	}
	
	for (i = 0; i < s.count; ++i)
	{
		if (s.stones[i] >= 2)
		{
			for (k = 1; k <= s.stones[i] - 1; ++k)
			{
				State s2 = s;
				s2.stones[i] = s.stones[i] - k;
				for (j = 0; j < s.count; ++j)
				{
					if (i != j)
					{
						for (t = 1; t <= s2.stones[i]; ++t)
						{
							State s3 = s2;
							s3.stones[i] -= t;
							s3.stones[j] += t;
							if (!Solve (s3))
							{
								//cached[s] = true;
								cachedState.push_back(s);
								cachedResult.push_back(true);
								return true;
							}
						}
					}
				}
			}
		}
	}

	//cached[s] = false;
	cachedState.push_back(s);
	cachedResult.push_back(false);
	return false;
}

int main()
{

	//freopen ("D:/VC Project/Test/Test/Data.txt", "r", stdin);
	//Solve ();

	int t = 0;
	scanf ("%d", &t);

	while (t!= 0)
	{
		State s;
		s.count = t;
		for (int j = 0; j < s.count; ++j)
		{
			scanf ("%d", &s.stones[j]);
		}

		if (Solve(s))
		{
			printf ("1");
		}
		else
		{
			printf("0");
		}
		printf ("\n");

		scanf ("%d", &t);
		
	}
	
	return 0;
}

• Re:TLE~~~牛人帮忙看看 (19) This_poet 2011-10-05 11:20:16