题目链接: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

评论