poj 1579 递归-记忆化搜索

2016-12-02 12:52:30来源:网络收集作者:Alex人点击

直接递归会重复计算一些值,如题所述会花费很长时间。最好的方法就是用记忆化搜索,用数组将值记录下来,当搜到已经计算过的值时直接使用就行了,避免再一次递归计算,这样会节省很多时间。


代码如下:http://blog.csdn.net/non_cease/article/details/6817914


#include
using namespace std;
const int size = 21;
int map[size][size][size];
void makeMap()
{
int a, b, c;
for(a = 0; a < size; a++)
for(b = 0; b < size; b++)
for(c = 0; c < size; c++)
{
if(a <= 0 || b <=0 || c <= 0)
map[a][b][c] = 1;
else if(a < b && b < c)
map[a][b][c] = map[a][b][c-1] + map[a][b-1][c-1] - map[a][b-1][c];
else
map[a][b][c] = map[a-1][b][c] + map[a-1][b-1][c] + map[a-1][b][c-1] - map[a-1][b-1][c-1];
}
}
int main()
{
int a, b, c, ans;
makeMap();
while(scanf("%d %d %d", &a, &b, &c) == 3)
{
if(a == -1 && b == -1 && c == -1)
break; if(a < 0 || b < 0 || c < 0)
ans = 1;
else if(a > 20 || b > 20 || c > 20)
ans = map[20][20][20];
else
ans = map[a][b][c];
printf("w(%d, %d, %d) = %d/n", a, b, c, ans);
}
return 0;
}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台