题目描述
Smith在P市的邮政局工作,他每天的工作是从邮局出发,到自己所管辖的所有邮筒取信件,然后带回邮局。他所管辖的邮筒非常巧地排成了一个的点阵(点阵中的间距都是相等的)。左上角的邮筒恰好在邮局的门口。 Smith是一个非常标新立异的人,他希望每天都能走不同的路线,但是同时,他又不希望路线的长度增加,他想知道他有多少条不同的路线可走。你的程序需要根据给定的输入,给出符合题意的输出。输入包括点阵的
和
的值,你需要根据给出的输入,计算出Smith可选的不同路线的总条数。
输入格式
只有一行。包括两个整数,表示了Smith管辖内的邮筒排成的点阵。
输出格式
只有一行,只有一个整数,表示Smith可选的不同路线的条数。
题目解析
这是插头DP的经典入门题了吧。题目所求即为网格图上经过所有点的哈密顿回路数量。
我们采用括号表示法来表示状态。表示左插头,
表示右插头,
表示无插头。
状态的转移比较复杂,需要仔细分析。设当前决策格的左侧和上侧的插头为,则有
1.
: 左侧和上侧都没有插头连入。因为每个格子必有两个插头,故向下、向右有插头,也就是开始一个新的连通分量,转移到
。
2.
: 左侧有插头连入,上侧没有。我们只需延续原来的连通分量,可以继续向右延伸转移到
,也可以转向下延伸转移到
,注意边界情况。
3.
: 类似2处理方式。
4.
: 上侧有插头连入,左侧没有。处理方式同2,3。
5.
: 类似4处理方式。
6.
: 左侧有左括号插头连入,上侧有有右括号插头连入。那么把它们连起来就圆满啦,刚好构成一条回路。但是注意这种情况只可发生在最后的格子(右下角),此时需要更新答案。
7.
: 左侧和上侧都有左括号插头连入。这时我们在合并两个联通分量,将它们连起来后,原来与上侧插头相匹配的右括号插头应该变成左括号插头,于是我们找到与上侧插头相匹配的右括号插头修改一下状态即可。
8.
: 左侧和上侧都有右括号插头连入。处理方式类似7,找到与左侧插头相匹配的左括号插头修改一下状态。
9.
: 左侧有右括号插头连入,上侧有左括号插头连入。就是将两连通分量连接起来,转移到
。
时间复杂度。膜一膜CDQ的著名论文《基于连通性状态压缩的动态规划问题》。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 |
/************************************************************** Problem: 1210 User: frank_c1 Language: C++ Result: Accepted Time:432 ms Memory:5420 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <cmath> #include <ctime> #include <cstdio> #include <vector> #include <string> #include <bitset> #include <cctype> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,x) for(int i=fr[x];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct ext { static const int BASE=100000000; static const int SIZE=50; int num[50],top; ext(int a=0) {*this=a;} int& operator[] (int k) {return num[k];} inline void clear() {top=0;memset(num,0,sizeof(num));} ext operator = (int x) { clear(); if(!x) num[++top]=0; else for(;x;num[++top]=x%BASE,x/=BASE); return *this; } inline void modify() { int i=1,x=0; for(;x || i<=top;i++) { x+=num[i]; num[i]=x%BASE;x/=BASE; } top=max(top,i-1); for(;top>1 && !num[top];top--); } inline void print() { printf("%d",num[top]); PER(i,top-1,1) printf("%08d",num[i]); } }; ext operator + (ext a,ext b) { ext c; c.top=max(a.top,b.top); REP(i,1,c.top) c[i]=a[i]+b[i]; c.modify(); return c; } void operator += (ext& a,ext b) {a=a+b;} int n,m; struct status { static const int mo=10007; int st[mo],cnt; int key[mo]; ext val[mo]; inline void clear() { cnt=0; memset(st,0,sizeof(st)); memset(key,-1,sizeof(key)); } status() {clear();} inline void print() { REP(i,1,cnt) { REP(k,0,m) { int c=(key[st[i]]>>(k<<1))&3; if(c==0) putchar('#'); if(c==1) putchar('('); if(c==2) putchar(')'); } putchar('\n'); } } ext& operator [] (int k) { int p=k%mo; while(key[p]!=k && key[p]!=-1) { p++;if(p>=mo) p-=mo; } if(key[p]==-1) st[++cnt]=p,key[p]=k,val[p]=0; return val[p]; } }; status f[2]; int lst=0; ext res=0; inline int info(int s,int p) { return (s>>((p-1)<<1))&3; } inline int qt(int s,int p) { int d=info(s,p)==1?1:-1,v=0; for(int i=p;;i+=d) { int c=info(s,i); if(c==1) v++; if(c==2) v--; if(v==0) return i; } return 0; } inline int modify(int s,int p,int nv) { int k=(p-1)<<1; return ((s|(3<<k))^(3<<k))|(nv<<k); } inline void calc(int i,int j) { int p=lst^1;f[p].clear(); REP(k,1,f[lst].cnt) { int c=f[lst].key[f[lst].st[k]]; ext v=f[lst].val[f[lst].st[k]]; int a=info(c,j),b=info(c,j+1); if(a==0 && b==0) { if(i==n || j==m) continue; c=modify(c,j,1);c=modify(c,j+1,2); f[p][c]+=v; } if(a!=0 && b==0) { if(i!=n) f[p][c]=f[p][c]+v; c=modify(c,j,0);c=modify(c,j+1,a); if(j!=m) f[p][c]+=v; } if(a==0 && b!=0) { if(j!=m) f[p][c]=f[p][c]+v; c=modify(c,j,b);c=modify(c,j+1,0); if(i!=n) f[p][c]+=v; } if(a==1 && b==1) { c=modify(c,qt(c,j+1),1); c=modify(c,j,0);c=modify(c,j+1,0); f[p][c]+=v; } if(a==2 && b==2) { c=modify(c,qt(c,j),2); c=modify(c,j,0);c=modify(c,j+1,0); f[p][c]+=v; } if(a==2 && b==1) { c=modify(c,j,0);c=modify(c,j+1,0); f[p][c]+=v; } if(a==1 && b==2) { if(i==n && j==m) res=res+v; } } lst=p; } int main() { read(n);read(m); if(n<m) swap(n,m); f[lst=0][0]=1; if(m==1) { printf("1\n"); return 0; } REP(i,1,n) { REP(j,1,m) calc(i,j); REP(k,1,f[lst].cnt) f[lst].key[f[lst].st[k]]<<=2; } res=res+res; res.print(); return 0; } |