這道題就是連通性狀態(tài)壓縮DP，復(fù)習(xí)了一下。

#include <cstdio> #include <iostream> #include <cstring> #include <map> using namespace std; long long dp[11][11][(1<<11)+1][2], n, m; long long dfs(int x, int y, int md, int right){long long &ret = dp[x][y][md][right];if(ret != -1) return ret;if(x >= n){if(!md) return ret = 1;else return ret = 0;}if(y >= m){if(right) return ret = 0;else return ret = dfs(x+1, 0, md, 0);}ret = 0;int now_Pos = 1 << y;if(right){if(md & now_Pos) return ret = 0;return ret = dfs(x, y+1, md, 0);}if(md & now_Pos){int n_md = md ^ now_Pos;return ret = dfs(x, y+1, n_md, right);}int n_md = md | now_Pos;return ret =( y+1 < m ? dfs(x, y+1, md, 1) : 0 )+ dfs(x, y+1, n_md, 0); } int main(){while(scanf("%d %d", &n, &m)!=EOF){if(n == 1 || m == 1){if((n % 2)^(m % 2))cout<<1<<endl;else cout<<0<<endl;continue;}memset(dp, -1, sizeof dp);cout<<dfs(0, 0, 0, 0)<<endl;} }

這道題如果寫遞歸版本的要TLE不知為何，話說我還沒有A

轉(zhuǎn)載于:https://www.cnblogs.com/JeremyGJY/p/5921736.html

總結(jié)

以上是生活随笔為你收集整理的【动态规划】[Uva11270]Tiling Dominoes的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。