codeforces 570 E. Pig and Palindromes (dp)
比赛的时候想到了是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
/*************************************************************************
> File Name: code/cf/#316/EE.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月15日 星期六 04时10分13秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int MOD=1E9+7;
25const int N=5E2+7;
26int n,m;
27char st[N][N];
1int dp[2][N][N];
2int main()
3{
4 scanf("%d %d",&n,&m);
5 for ( int i = 1 ; i <= n ; i++)
6 {
7 scanf("%s",&st[i][1]);
8 }
9 // dp[0][1][n]= st[1][1]==st[n][m];
10 if (st[1][1]==st[n][m])
11 {
12 dp[0][1][n]=1;
13 }
14 else
15 {
16 dp[0][1][n]=0;
17 }
18 int cur = 0;
19 int mx = (m+n-2)/2;
20 for ( int step = 1 ; step <= mx ; step++)
21 {
22 cur = cur ^ 1;
23 for (int i = 1 ; i<= n ; i++)
24 {
25 for ( int j = 1 ; j <= n ; j++ )
26 {
27 dp[cur][i][j] =0 ;
28 }
29 }
1 for ( int x1 = 1 ; x1 <= n&&x1-1<=step ;x1++)
2 {
3 for ( int x2 = n ; x2>=1 &&n-x2<=step ;x2--)
4 {
5 int y1 = 1+step-(x1-1);
6 int y2 = m-step+(n-x2); //由x1,x2 可以计算出y1,y2
7 if (st[x1][y1]==st[x2][y2])
8 {
9 dp[cur][x1][x2] = (dp[cur][x1][x2] + dp[cur^1][x1][x2])%MOD;
10 dp[cur][x1][x2] = (dp[cur][x1][x2] + dp[cur^1][x1][x2+1])%MOD;
11 dp[cur][x1][x2] = (dp[cur][x1][x2] + dp[cur^1][x1-1][x2])%MOD;
12 dp[cur][x1][x2] = (dp[cur][x1][x2] + dp[cur^1][x1-1][x2+1])%MOD;
13 }//只有当前pic 相同的时候才转移
14 }
15 }
16 }
17 int ans = 0;
18 for ( int i = 1 ; i<= n ; i++ )
19 {
20 ans = (ans + dp[cur][i][i]) % MOD;
21 }
22 if ((m+n)%2)
23 {
24 for ( int i = 1 ; i<= n-1 ; i++)
25 {
26 ans = (ans + dp[cur][i][i+1])%MOD;
27 }
28 }
29 cout<<ans<<endl;
return 0;
}