首页 > 代码库 > 51Nod 1503 猪和回文
51Nod 1503 猪和回文
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1503
思路：
没想到要用DP去解决。
题目是从起点出发走，我们可以从起点和终点各出发一个点，每次两个点各走一步，当然这两步所对应的字符是要一样的。
于是，定义d[step][x1][y2][x2][y2]，表示第step时第一个点走到（x1，y1），第二个点走到（x2，y2）时（当然了，这两个点的字符肯定是相同的）的方法数。
因为此时的方法数是基于上一步的情况，所以用滚动数组即可，而y又可根据x和step求出，所以可以将数组维数缩小至3维。
注意n+m是奇数时的情况，需要额外计数。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 10 const int MOD=1e9+7;11 12 int n,m;13 char map[505][505];14 int d[2][505][505];15 16 void add(int &x,int y)17 {18 x=(x+y)%MOD;19 }20 21 int main()22 {23 //freopen("D:\\input.txt","r",stdin);24 while(~scanf("%d%d",&n,&m))25 {26 getchar();27 for(int i=1;i<=n;i++)28 {29 for(int j=1;j<=m;j++)30 scanf("%c",&map[i][j]);31 getchar();32 }33 34 int cur=0;35 d[0][1][n]=(map[1][1]==map[n][m]);36 37 for(int step=1;step<=(n+m-2)/2;step++)38 {39 cur^=1;40 for(int i=1;i<=n;i++)41 for(int j=1;j<=n;j++)42 d[cur][i][j]=0;43 44 for(int x1=1;x1<=n && x1-1<=step;x1++)45 for(int x2=n;x2>=1 && n-x2<=step;x2--)46 {47 int y1 = 1 + step - (x1 - 1);48 int y2 = m - (step - (n - x2));49 if(map[x1][y1]!=map[x2][y2]) continue;50 add(d[cur][x1][x2],d[cur^1][x1][x2]);51 add(d[cur][x1][x2],d[cur^1][x1-1][x2]);52 add(d[cur][x1][x2],d[cur^1][x1][x2+1]);53 add(d[cur][x1][x2],d[cur^1][x1-1][x2+1]);54 }55 }56 int ans=0;57 for(int i=1;i<=n;i++)58 add(ans,d[cur][i][i]);59 if((n+m)%2)60 for(int i=1;i<n;i++)61 add(ans,d[cur][i][i+1]);62 printf("%d\n",ans);63 }64 }
51Nod 1503 猪和回文
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。