看題解解的。將著色方案映射為40*40*5*5*5*5*2個狀態(tài)，40*40表示n*m,5*5*5*5表示上下左右相鄰塊的顏色，0表示未著色。
2表示橫切或者豎切。
基本思路是記憶化搜索然后去重，關(guān)鍵點是可能未切前當前塊已經(jīng)著色了。
1 /* 4363 */
2 #include <iostream>
3 #include <sstream>
4 #include <
string>
5 #include <map>
6 #include <queue>
7 #include <
set>
8 #include <stack>
9 #include <vector>
10 #include <deque>
11 #include <algorithm>
12 #include <cstdio>
13 #include <cmath>
14 #include <ctime>
15 #include <cstring>
16 #include <climits>
17 #include <cctype>
18 #include <cassert>
19 #include <functional>
20 #include <iterator>
21 #include <iomanip>
22 using namespace std;
23 //#pragma comment(linker,"/STACK:102400000,1024000")
24
25 #define sti set<int>
26 #define stpii set<pair<int, int> >
27 #define mpii map<int,int>
28 #define vi vector<int>
29 #define pii pair<int,int>
30 #define vpii vector<pair<int,int> >
31 #define rep(i, a, n) for (int i=a;i<n;++i)
32 #define per(i, a, n) for (int i=n-1;i>=a;--i)
33 #define clr clear
34 #define pb push_back
35 #define mp make_pair
36 #define fir first
37 #define sec second
38 #define all(x) (x).begin(),(x).end()
39 #define SZ(x) ((int)(x).size())
40 #define lson l, mid, rt<<1
41 #define rson mid+1, r, rt<<1|1
42
43 const int mod = 1e9+
7;
44 int dp[
41][
41][
5][
5][
5][
5][
2];
45
46 int calc(
int x,
int y,
int u,
int d,
int l,
int r,
int dir) {
47 if (dp[x][y][u][d][l][r][dir] >=
0)
48 return dp[x][y][u][d][l][r][dir];
49
50 int& ret =
dp[x][y][u][d][l][r][dir];
51
52 ret =
0;
53 if ((x==
1&&dir==
0) || (y==
1&&dir==
1)) {
54 rep(i,
1,
5)
55 if (i!=u && i!=d && i!=l && i!=
r)
56 ++
ret;
57 return ret;
58 }
59
60 if (dir) {
61 rep(i,
1, y) {
62 rep(j,
1,
5) {
63 if (j!=u && j!=d && j!=
l) {
64 ret = (ret + calc(x, y-i, u, d, j, r,
0)) %
mod;
65 }
66 if (j!=u && j!=d && j!=
r) {
67 ret = (ret + calc(x, i, u, d, l, j,
0)) %
mod;
68 }
69 }
70 }
71
72 int tmp =
0;
73 rep(i,
1,
5) {
74 if (i!=u && i!=d && i!=
l) {
75 rep(j,
1,
5) {
76 if (j!=u && j!=d && j!=r && j!=
i)
77 ++
tmp;
78 }
79 }
80 }
81
82 ret = (ret + mod - tmp*(y-
1)) %
mod;
83 rep(i,
1,
5)
84 if (i!=u && i!=l && i!=r && i!=
d)
85 ++
ret;
86
87 ret %=
mod;
88 }
else {
89 rep(i,
1, x) {
90 rep(j,
1,
5) {
91 if (j!=u && j!=l && j!=
r) {
92 ret = (ret + calc(x-i, y, j, d, l, r,
1)) %
mod;
93 }
94 if (j!=d && j!=l && j!=
r) {
95 ret = (ret + calc(i, y, u, j, l, r,
1)) %
mod;
96 }
97 }
98 }
99
100 int tmp =
0;
101 rep(i,
1,
5) {
102 if (i!=u && i!=l && i!=
r) {
103 rep(j,
1,
5) {
104 if (j!=d && j!=l && j!=r && j!=
i)
105 ++
tmp;
106 }
107 }
108 }
109
110 ret = (ret + mod - tmp*(x-
1)) %
mod;
111 rep(i,
1,
5)
112 if (i!=u && i!=l && i!=r && i!=
d)
113 ++
ret;
114
115 ret %=
mod;
116 }
117
118 return ret;
119 }
120
121 int main() {
122 ios::sync_with_stdio(
false);
123 #ifndef ONLINE_JUDGE
124 freopen(
"data.in",
"r", stdin);
125 freopen(
"data.out",
"w", stdout);
126 #endif
127
128 int t;
129 int n, m;
130 int ans;
131
132 memset(dp, -
1,
sizeof(dp));
133 scanf(
"%d", &
t);
134 while (t--
) {
135 scanf(
"%d %d", &n, &
m);
136 ans = calc(n, m,
0,
0,
0,
0,
0);
137 printf(
"%d\n", ans);
138 }
139
140 #ifndef ONLINE_JUDGE
141 printf(
"time = %d.\n", (
int)clock());
142 #endif
143
144 return 0;
145 }
?
轉(zhuǎn)載于:https://www.cnblogs.com/bombe1013/p/5201289.html
總結(jié)
以上是生活随笔為你收集整理的【HDOJ】4363 Draw and paint的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
