AC HDU1693 不能再简单了的插头DP
1 #include <cstdio>
2 #include <fstream>
3 #include <iostream>
4
5 #include <cstdlib>
6 #include <cstring>
7 #include <algorithm>
8 #include <cmath>
9
10 #include <queue>
11 #include <vector>
12 #include <map>
13 #include <set>
14 #include <stack>
15 #include <list>
16
17 typedef unsigned int uint;
18 typedef long long int ll;
19 typedef unsigned long long int ull;
20 typedef double db;
21 typedef long double ldb;
22
23 using namespace std;
24
25 inline int getint()
26 {
27 int res=0;
28 char c=getchar();
29 bool mi=false;
30 while((c<'0' || c>'9')/* && !feof(stdin)*/) mi=(c=='-'),c=getchar();
31 while('0'<=c && c<='9'/* && !feof(stdin)*/) res=res*10+c-'0',c=getchar();
32 return mi ? -res : res;
33 }
34 inline ll getll()
35 {
36 ll res=0;
37 char c=getchar();
38 bool mi=false;
39 while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
40 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
41 return mi ? -res : res;
42 }
43
44 //==============================================================================
45 //==============================================================================
46 //==============================================================================
47 //==============================================================================
48
49
50
51 int n,m;
52 int M[13][13];
53
54 ull d[13][13][8192];
55
56 inline uint get(uint k,int l){ return k&(1<<l); }
57 inline bool exist(uint k,int l) { return get(k,l)>0; }
58 inline uint clr(uint k,int l){ return k&(0xFFFFFFFF-(1<<l)); }
59 inline uint ins(uint k,int l){ return k|(1<<l); }
60 inline uint trs(uint k,int l,int v)
61 {
62 switch(v)
63 {
64 case 0: return clr(clr(k,m),l);
65 case 1: return ins(clr(k,m),l);
66 case 2: return clr(ins(k,m),l);
67 case 3: return ins(ins(k,m),l);
68 default:return k;
69 }
70 }
71 void prt(uint k) { for(int i=0;i<=m;i++) printf("%d",exist(k,i)); }
72
73 int main()
74 {
75 for(int T=getint(),cc=0;T;T--)
76 {
77 n=getint();
78 m=getint();
79 for(int i=1;i<=n;i++)
80 for(int j=1;j<=m;j++) M[i][j]=getint();
81
82 for(int i=1;i<=n;i++) for(int j=0;j<=m;j++)
83 memset(d[i][j],0,sizeof(ll)*(1<<(m+1)));
84
85 d[0][m][0]=1; //filled of blocks.
86
87 for(int i=1;i<=n;i++) //foreach line
88 {
89 for(int k=0;k<1<<m;k++)
90 d[i][0][k]=d[i-1][m][k];
91
92 for(int j=1;j<=m;j++) //foreach column
93 {
94 int t=j-1;
95 for(int k=0;k<1<<(m+1);k++) //foreach state
96 {
97 ull&D=d[i][j][k];
98 bool a=exist(k,t);
99 bool b=exist(k,m);
100
101 if(M[i][j])
102 {
103 if(!a && !b) D=d[i][j-1][trs(k,t,3)];
104 else if(a && b) D=d[i][j-1][trs(k,t,0)];
105 else D=d[i][j-1][trs(k,t,1)]+d[i][j-1][trs(k,t,2)];
106 }
107 else
108 {
109 if(a || b) D=0;
110 else D=d[i][j-1][trs(k,t,0)];
111 }
112 }
113 }
114 }
115 printf("Case %d: There are %I64u ways to eat the trees.
",++cc,d[n][m][0]);
116 }
117
118
119 return 0;
120 }
看题解发现几乎所有人都在用格子的左上轮廓表示状态,而我在用右下...于是乎又不能照抄代码了TAT
推转移推了好久Orz....虽然说这个题的转移在常规插头DP中显然不算难Orz...
另外我设了一个固定的位来表示竖直的那一条轮廓线状态......但是好像其他题解都是直接把它当做普通轮廓线处理?
咦我好像用了I64u..居然没PE?
...