\u7ed9\u5b9a\u4e00\u5757 n \u00d7 m \u7684\u7535\u8def\u677f\uff0c\u4e0a\u9762\u6709\u4e00\u4e9b\u4f4d\u7f6e\u662f\u574f\u7684\uff0c\u95ee\u6700\u591a\u53ef\u4ee5\u9576\u5d4c\u591a\u5c112 \u00d7 3\u5927\u5c0f\u7684\u82af\u7247\u3002
\n\uff081 < = n <= 150, 1 <= m <= 10 …\uff09
\n<\/p>\n
…<\/p>\n
\r\n#include <iostream>\r\nusing namespace std;\r\nconst int hh = 150, ww = 10, _W = 16, ss = 1123; \/\/1 << 20; \/\/?\r\nconst int _A = (1 << ww) - 1, _B = _A << _W;\r\nint O[hh+1];\r\nint h, w, s0, s1, s2, up;\r\nshort ans, b;\r\n\r\nstruct hashTable {\r\n\tint state[ss], head[ss], next[ss], sz;\r\n\tshort key[ss];\r\n\t\r\n\tinline void clear() {\r\n\t\tsz = 0;\r\n\t\tmemset(head, -1, sizeof(head));\r\n\t}\r\n\tinline void insert(int s0, int s1, short val) {\r\n\t\tint s = s0 | s1 | s1 << _W;\r\n\t\tint x = s % ss;\r\n\t\tfor ( int it = head[x] ; it != -1 ; it = next[it] ) {\r\n\t\t\tif ( state[it] == s ) {\r\n\t\t\t\tkey[it] = max(key[it], val);\r\n\t\t\t\treturn;\r\n\t\t\t}\r\n\t\t}\r\n\t\tstate[sz] = s, key[sz] = val;\r\n\t\tnext[sz] = head[x];\r\n\t\thead[x] = sz++;\r\n\t}\r\n\tinline short search(int s){\r\n\t\tint x = s % ss;\r\n\t\tfor ( int it = head[x] ; it != -1 ; it = next[it])\r\n\t\t\tif ( state[it] == s ) return key[it];\r\n\t\treturn 0;\r\n\t}\r\n} H[2] , *src , *des;\r\n\r\n\r\nvoid dfs(int j, short d, int s1, int s2){\r\n\twhile (true){\r\n\t\tif (j == w){\r\n\t\t\tdes->insert(s1, s2, b + d);\r\n\t\t\treturn;\r\n\t\t}\r\n\t\telse {\r\n\t\t\tif (j < w-2 && !(s0 & 7 << j))\r\n\t\t\t\tdfs(j+3, d+1, s1 | 7 << j, s2);\r\n\t\t\tif (j < w-1 && !(s0 & 3 << j) && !(s2 & 3 << j))\r\n\t\t\t\tdfs(j+2, d+1, s1, s2 | 3 << j);\r\n\t\t}\r\n\t\tj++;\r\n\t}\r\n}\r\n\r\n\r\nvoid solve(){\r\n\tsrc = H, des = src + 1, des->clear(), des->insert(O[0], O[1], 0);\r\n\t\r\n\tfor (int i = 0; i < h - 1; i ++){\r\n\t\tswap(src, des), des->clear(), s2 = O[i+2];\r\n\t\tfor (int it = 0; it < src->sz; it++){\r\n\t\t\ts0 = src->state[it] & _A | up, s1 = (src->state[it] & _B) >> _W;\r\n\t\t\tb = src->key[it], dfs(0, 0, s1, s2);\r\n\t\t}\r\n\t\t\/\/cout << des->sz << endl;\r\n\t}\r\n\t\r\n\tans = 0;\r\n\tfor (int it = 0; it < des->sz; it++)\r\n\t\tans = max(ans, des->key[it]);\r\n}\r\n\r\nvoid init(){\r\n\tint t;\r\n\tscanf("%d%d%d", &h, &w, &t); \r\n\tmemset(O, 0, sizeof(O));\r\n\t\r\n\tint x, y;\r\n\tfor (int i=0;i<t;i++){\r\n\t\tscanf("%d%d", &x, &y), x--, y--;\r\n\t\tO[x] |= 1 << y;\r\n\t}\r\n\t\r\n\tup = 1 << w;\r\n\tO[h] = up - 1;\r\n}\r\n\r\n\r\nint main(){\r\n\t\/\/freopen("in.txt", "r", stdin);\r\n\tint T; cin >> T;\r\n\twhile (T--){\r\n\t\tinit(); solve();\r\n\t\tcout << ans << endl;\r\n\t}\r\n}\r\n<\/pre>\nExternal link :<\/h3>\n