Note: This article is available in Chinese only. 本文暂无英文版本。
View original
比赛的时候想到了是dp搞…
不过dp废…..
可能更多的是心理上…
这道题并不怎么难想,但是以觉得是dp,就给了自己一种暗示…这题我搞不出来…
实际上,我把cA掉的时候应该还有一个小时十分钟左右的样子…
d题没啥思路,所以我有大概一个小时的时间可以搞e…未必就搞不出来.
还有因为答案很大要取模,感觉一般取模的题,要么是数学,要么是像dp这种有递推式子的.
这道题的思路是:
因为要形成回文串,我们可以从两边往中间走,保证每一步都相同.
dp[i][x1][x2] 表示路径长度为i,左上角出发到达x坐标为x1,又下角出发到达x坐标为x2,且两条路径上对应的字母都相同的方案数.
然后判断当前格子的字母是否一样,如果一样,则考虑转移.
由于从左上角出发可以往下往右,从右下角出发可以往上往左,排列组合,所以当前状态和之前的四种状态有关.
由因为这步的状态只和上以步的四种状态有关,所以路径长度那以维要滚动掉不然会MLE
dp方程为 dp[cur][x1][x2]=(dp[cur^1][x1][x2],dp[cur^1][x1-1][x2],dp[cur^1][x1][x2+1],dp[cur^1][x1-1][x2+1])%MOD;
然后注意由于(m+n) 的奇偶性,答案会有所不同.
根据奇偶性判断从两端出发是到两个相邻的格子还是到同一个格子.
初始化的话如果(1,1)和{n,m}点的字母一样那么 dp[0][1][n] 为1,否则为0.
其他点显然都为0
1/*************************************************************************
2 > File Name: code/cf/#316/EE.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月15日 星期六 04时10分13秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31const int MOD=1E9+7;
32const int N=5E2+7;
33int n,m;
34char st[N][N];
35
36int dp[2][N][N];
37int main()
38{
39 scanf("%d %d",&n,&m);
40 for ( int i = 1 ; i <= n ; i++)
41 {
42 scanf("%s",&st[i][1]);
43 }
44 // dp[0][1][n]= st[1][1]==st[n][m];
45 if (st[1][1]==st[n][m])
46 {
47 dp[0][1][n]=1;
48 }
49 else
50 {
51 dp[0][1][n]=0;
52 }
53 int cur = 0;
54 int mx = (m+n-2)/2;
55 for ( int step = 1 ; step <= mx ; step++)
56 {
57 cur = cur ^ 1;
58 for (int i = 1 ; i<= n ; i++)
59 {
60 for ( int j = 1 ; j <= n ; j++ )
61 {
62 dp[cur][i][j] =0 ;
63 }
64 }
65
66 for ( int x1 = 1 ; x1 <= n&&x1-1<=step ;x1++)
67 {
68 for ( int x2 = n ; x2>=1 &&n-x2<=step ;x2--)
69 {
70 int y1 = 1+step-(x1-1);
71 int y2 = m-step+(n-x2); //由x1,x2 可以计算出y1,y2
72 if (st[x1][y1]==st[x2][y2])
73 {
74 dp[cur][x1][x2] = (dp[cur][x1][x2] + dp[cur^1][x1][x2])%MOD;
75 dp[cur][x1][x2] = (dp[cur][x1][x2] + dp[cur^1][x1][x2+1])%MOD;
76 dp[cur][x1][x2] = (dp[cur][x1][x2] + dp[cur^1][x1-1][x2])%MOD;
77 dp[cur][x1][x2] = (dp[cur][x1][x2] + dp[cur^1][x1-1][x2+1])%MOD;
78 }//只有当前pic 相同的时候才转移
79 }
80 }
81 }
82 int ans = 0;
83 for ( int i = 1 ; i<= n ; i++ )
84 {
85 ans = (ans + dp[cur][i][i]) % MOD;
86 }
87 if ((m+n)%2)
88 {
89 for ( int i = 1 ; i<= n-1 ; i++)
90 {
91 ans = (ans + dp[cur][i][i+1])%MOD;
92 }
93 }
94 cout<<ans<<endl;
95
96 return 0;
97}