LGP3126题解

这道题还有点意思。

路径要求是一个回文串，回文串立马枚举中点。中点只可能在对角线上。

枚举对角线上的一个点，然后两边的路径必须完全相同。

既然路径上的字符必须完全相同，那么每个前缀也必须完全相同。

考虑 DP。设 \(dp[x1][y1][x2][y2]\) 表示左上方的路径终点在 \((x1,y1)\)，右下方的路径终点在 \((x2,y2)\)。

这状态看上去就可以优化，\(dp[k][x1][x2]\)，表示 \((x1,k-x1)\) 和 \((x2,k-x2)\)。

然后随便转移一下就差不多了吧。

复杂度 \(O(n^3)\)，可以通过。

需要注意滚动数组。

#include<cstdio>

typedef unsigned ui;

const ui M=505,mod=1e9+7;

ui n,dp[2][M][M];char q[M][M],p[M][M];

signed main(){

	ui ans(0);

	scanf("%u",&n);

	for(ui i=1;i<=n;++i)scanf("%s",q[i]+1);

	for(ui i=1;i<=n;++i)for(ui j=1;j<=n;++j)p[i][j]=q[n-i+1][n-j+1];

	if(q[1][1]!=p[1][1])return printf("0"),0;

	dp[0][1][1]=1;

	for(ui now(1),lst(0),i=3;i<=n+1;now^=lst^=now^=lst,++i){

		for(ui x1=1;x1<i;++x1)for(ui x2=1;x2<i;++x2)dp[now][x1][x2]=0;

		for(ui x1=1;x1<i;++x1){

			for(ui x2=1;x2<i;++x2)if(q[x1][i-x1]==p[x2][i-x2]){

				dp[now][x1][x2]=(dp[lst][x1][x2]+dp[lst][x1-1][x2]+dp[lst][x1][x2-1]+dp[lst][x1-1][x2-1])%mod;

			}

		}

	}

	for(ui i=1;i<=n;++i)ans=(ans+dp[n+1&1][i][n+1-i])%mod;

	printf("%u",ans);

}

巴特西

LGP3126题解

最新文章

热门文章