比赛 20130923 评测结果 MEMMMMMMMM
题目名称 邮递员 最终得分 0
用户昵称 mikumikumi 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2015-10-12 21:32:10
显示代码纯文本
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. using namespace std;
  6. const int SIZEN=10,SIZEM=20;
  7. typedef long long LL;
  8. int N,M;//N是列
  9. LL f[SIZEM][SIZEN][1148576]={0};
  10. class poi
  11. {
  12. public:
  13. int s[SIZEN];//0-无,1-左,2-右
  14. int x,y,k;
  15. poi(){}
  16. int val()//状态码
  17. {
  18. int ans=0;
  19. for(int i=1;i<=N;i++)
  20. {
  21. ans<<=2;
  22. ans+=s[i];
  23. }
  24. ans<<=2;ans+=k;
  25. return ans;
  26. }
  27. void clear()
  28. {
  29. x=y=k=0;
  30. memset(s,0,sizeof(s));
  31. }
  32. bool change(int U,int D,int L,int R)
  33. {
  34. if(U&&x==1) return 0;
  35. if(L&&y==1) return 0;
  36. if(R&&y==N) return 0;
  37. if(D&&x==M) return 0;
  38. if(L!=k) return 0;
  39. if(U!=s[y]) return 0;
  40. s[y]=D;
  41. k=R;
  42. y++;
  43. return 1;
  44. }
  45. void print()
  46. {
  47. cout<<x<<" "<<y<<" "<<k<<endl;
  48. for(int i=1;i<=N;i++) cout<<s[i]<<" ";
  49. cout<<endl;
  50. cout<<endl;
  51. }
  52. };
  53. void read()
  54. {
  55. scanf("%d%d",&N,&M);
  56. }
  57. LL DP(poi S)
  58. {
  59. if(f[S.x][S.y][S.val()]) return f[S.x][S.y][S.val()];
  60. if(S.y>N)
  61. {
  62. S.y=1;S.k=0;
  63. S.x++;
  64. }
  65. if(S.x>M) return 1;
  66. poi T;
  67. LL ans=0;
  68. for(int i=1;i<=2;i++)
  69. {
  70. for(int j=1;j<=2;j++)
  71. {
  72. if(i==j) continue;
  73. T=S;if(T.change(i,j,0,0)) ans+=DP(T);
  74. T=S;if(T.change(i,0,j,0)) ans+=DP(T);
  75. T=S;if(T.change(i,0,0,j)) ans+=DP(T);
  76. T=S;if(T.change(0,i,j,0)) ans+=DP(T);
  77. T=S;if(T.change(0,i,0,j)) ans+=DP(T);
  78. T=S;if(T.change(0,0,i,j)) ans+=DP(T);
  79. }
  80. }
  81. //cout<<ans<<endl;
  82. //S.print();
  83. f[S.x][S.y][S.val()]=ans;
  84. return ans;
  85. }
  86. int main()
  87. {
  88. freopen("postman.in","r",stdin);
  89. freopen("postman.out","w",stdout);
  90. read();
  91. poi S;
  92. S.clear();
  93. S.x=1;S.y=1;
  94. LL ans=DP(S);
  95. printf("%I64d",ans);
  96. return 0;
  97. }