//Codeforces #316 E Pig and Palindromes////题目大意:////给你一张地图,n*m每个点是一个字母,现在从(0,0)出发,//每次只能往右或者往下走,求走到(n-1,m-1)形成回文串的方法数.////解题思路:////动态规划.首先.如果起点和终点的字母不相同,那么肯定//不能形成回文串,直接输出0.对于能形成回文串.我们设状态//d(step,i,j)表示走了step步,从第0行走到i行,第n-1行走到j行的//能形成回文串的方法数.//1)从左上方只能往右,或者下方走//2)从右下方只能往左,或者上方走//我们采用刷表法从d(step,i,j)分别对////d(step+1,i+1,j) 下,左//d(step+1,i+1,j-1) 下,上//d(step+1,i,j); 右,左//d(step+1,i,j-1); 右,上////由于内存的限制,而状态只依赖于上一步的状态.则我们只需要step开2维即可//或者用一个temp数组暂时存储.////最后的结果也要分所形成的回文串的奇偶来判断.////回文串奇数:////这样一定是到了一个共同的字母,即中间的字母就相遇了.即走到了同一行//累加d(i,i).输出结果.////回文串偶数:////这样最后一定是双方同时走一步正好相邻.换而言之相遇的结果只能是左上方//走到某个点x(i,j),同时右下方的点走到了x的右边一个或者下边一个.这时候判断//并做累加就好了.////感悟:////这道题,虽然题目的意思很简单,但是对于我看来,实在是太复杂了,哎,dp的弱才啊//我开始看的是红名爷的代码,有很多疑惑的地方,最后MY一眼看出就是SB题目,给我讲了//状态,转移.还有边界等一系列.可以说是手把手的教.哎,卡了这么久,总算是能够真正//的理解红名爷还有MY的思路了.差距就是这么大啊,小子在此感谢MY还有红名爷~~~//哎,不说什么了,继续加油吧!FIGHTING#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const ll MOD = 1e9 + 7;const int maxn = 508;char g[maxn][maxn];ll d[maxn][maxn];ll tmp[maxn][maxn];int n,m;bool ok(int x1,int y1,int x2,int y2){if (x1<n && y1<m && x2>=0 && y2>=0 && g[x1][y1] == g[x2][y2])return true;return false;}void add(ll &x ,ll y){x += y;if (x>=MOD)x -= MOD;}void print(){for (int i=0;i<n;i++){for (int j=0;j<m;j++)cout << d[i][j] << " ";cout << endl;}}void input(){for (int i=0;i<n;i++)scanf("%s",g[i]);if (g[0][0]!=g[n-1][m-1]){puts("0");return ;}memset(d,0,sizeof(d));memset(tmp,0,sizeof(tmp));d[0][n-1] = 1;int s = n + m – 2;for (int step = 0; step < s/2;step++){for (int x0 = 0;x0 < n && step – x0 >=0;x0++){int y0 = step – x0;for (int x1 = 0;x1 < n && s – step – x1>=0 ;x1++){int y1 = s – step – x1;if (ok(x0+1,y0,x1-1,y1)){add(tmp[x0+1][x1-1],d[x0][x1]);}if (ok(x0+1,y0,x1,y1-1)){add(tmp[x0+1][x1],d[x0][x1]);}if (ok(x0,y0+1,x1-1,y1)){add(tmp[x0][x1-1],d[x0][x1]);}if (ok(x0,y0+1,x1,y1-1)){add(tmp[x0][x1],d[x0][x1]);}}}for (int i=0;i<n;i++)for (int j=0;j<n;j++){d[i][j] = tmp[i][j];tmp[i][j] = 0;}}if (n + m – 1 & 1){ll ans = 0;for (int i=0;i<n;i++){add(ans,d[i][i]);}printf("%I64d\n",ans);}else {ll ans = 0;s /= 2;for (int i=0;i<n;i++){ // i表示走到了i行if (s – i + 1 < m && g[i][s-i]==g[i][s-i+1]) //判断走到该点的右边是否与之相同add(ans,d[i][i]);if (i + 1 < n && g[i][s-i] == g[i+1][s-i]) // 判断走到该点的下边是否与之相同add(ans,d[i][i+1]);}printf("%I64d\n",ans);}}int main(){//freopen("1.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){input();}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
累死累活不说，走马观花反而少了真实体验，
