正文

pku1351 动规——记忆化搜索2008-05-22 09:35:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/insky/35323.html

分享到:

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1351
/**********pku1351************
* 动规——记忆化搜索
* a[n][p][k][u]
* n: 统计了几个slot
* p: 当前取道那些值 按位存储p=7(0111)表示已经取到1,2,3
* k: 最后一个值
* u: 是否满足条件1
* 注意答案会超过32位整数
******************************/
#include <stdio.h>
#include <memory.h>

__int64 a[20][16][5][2];
int flag[5] = {0,1,2,4,8};

void init()
{
	int i;
	memset(a,-1,sizeof(a));
	for(i=0;i<=15;i++)
	{
		a[1][i][1][1] = a[1][i][2][1] = a[1][i][3][1] = a[1][i][4][1] = 0;
		a[1][i][1][0] = a[1][i][2][0] = a[1][i][3][0] = a[1][i][4][0] = 0;
	}
	a[1][1][1][0] = 1;
	a[1][2][2][0] = 1;
	a[1][4][3][0] = 1;
	a[1][8][4][0] = 1;
}

__int64 ado(int n,int p,int k,int u)
{
	int t;
	if(n<=0) return 0;
	if(a[n][p][k][u]!=-1) return a[n][p][k][u];
	a[n][p][k][u] = 0;
	if((p&flag[k])==0) return 0; /*p不包含k,直接返回0*/
	t = p&~flag[k];
	if(u==0)
	{
		if(k==1)
		{
			a[n][p][k][u] += ado(n-1,p,1,0) + ado(n-1,p,2,0) + ado(n-1,p,3,0);
			a[n][p][k][u] += ado(n-1,t,1,0) + ado(n-1,t,2,0) + ado(n-1,t,3,0);
		}
		else if(k==4)
		{
			a[n][p][k][u] += ado(n-1,p,2,0) + ado(n-1,p,3,0) + ado(n-1,p,4,0);
			a[n][p][k][u] += ado(n-1,t,2,0) + ado(n-1,t,3,0) + ado(n-1,t,4,0);
		}
		else
		{
			a[n][p][k][u] += ado(n-1,p,1,0) + ado(n-1,p,2,0) + ado(n-1,p,3,0) + ado(n-1,p,4,0);
			a[n][p][k][u] += ado(n-1,t,1,0) + ado(n-1,t,2,0) + ado(n-1,t,3,0) + ado(n-1,t,4,0);
		}
	}
	else
	{
		a[n][p][k][u] += ado(n-1,p,1,1) + ado(n-1,p,2,1) + ado(n-1,p,3,1) + ado(n-1,p,4,1);
		a[n][p][k][u] += ado(n-1,t,1,1) + ado(n-1,t,2,1) + ado(n-1,t,3,1) + ado(n-1,t,4,1);
		if(k==1)
		{
			a[n][p][k][u] += ado(n-1,p,4,0);
			a[n][p][k][u] += ado(n-1,t,4,0);
		}
		if(k==4)
		{
			a[n][p][k][u] += ado(n-1,p,1,0);
			a[n][p][k][u] += ado(n-1,t,1,0);
		}
	}
	return a[n][p][k][u];
}

int main()
{
	int n,i;
	__int64 sum;
	init();
	while(scanf("%d",&n)&&n!=-1)
	{
		for(i=1,sum=0;i<=4;i++)
		{
			sum += ado(n,7,i,1);
			sum += ado(n,11,i,1);
			sum += ado(n,13,i,1);
			sum += ado(n,14,i,1);
			sum += ado(n,15,i,1);
		}
		printf("%d: %I64d\n",n,sum);
	}
	return 0;
}
本栏目所有文章均为原创,转载请注明来源:http://insky.programfan.com

阅读(1876) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册