hdu 5617 Jam's maze(双线程dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5617

官方题解：

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int inf = 0x3f3f3f3f; const int mod = 5201314; int n,dp[2][505][505]; char Map[505][505];void add(int &x,int y) {x += y;if(x >= mod) x -= mod; }int main() {int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i = 1;i <= n;i++)scanf("%s",Map[i]+1);int p = 0;memset(dp[p],0,sizeof(dp[p]));dp[p][1][n] = Map[1][1] == Map[n][n];for(int i=1;i<n;i++){memset(dp[!p],0,sizeof(dp[!p]));for(int x1 = 1;x1 <= i + 1; x1++){for(int x2 = n; x2 >= n - i; x2--){int y1 = i + 2 - x1;int y2 = 2 * n - i - x2;if(Map[x1][y1] != Map[x2][y2]) continue;add(dp[!p][x1][x2],dp[p][x1][x2]);add(dp[!p][x1][x2],dp[p][x1][x2+1]);add(dp[!p][x1][x2],dp[p][x1-1][x2+1]);add(dp[!p][x1][x2],dp[p][x1-1][x2]);}}p ^= 1;}int ans = 0;for(int i = 1; i <= n; i++)add(ans,dp[p][i][i]);printf("%d\n",ans);}return 0; }

总结

以上是生活随笔为你收集整理的hdu 5617 Jam's maze(双线程dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。