题解 P3126 【[USACO15OPEN]回文的路径Palindromic Paths】

· · 题解

思路和其它题解大致相同，本题解主要是详细说明状态转移方式以及和其它题解不同的滚动数组方式。

总体思路

因为是回文串，所以不如从左上角和右下角同时向中间走，每一步必须走字母相同的格子，最后到中间汇合就可以得到方案数了。

如果分别枚举两个点的坐标则是O(n^4)的，会超时，但可以看出步数相同时两个点的横纵坐标和有一定规律，分别为2+step和2n-step，因此只要枚举步数和两点纵（横）坐标即可。

状态表示

f(i,j,k)表示:

的方案总数

状态转移

因为只有两点字母相同时才能走，因此当两点字母不同时方案数为0，否则为每个可以走过来的状态的方案数之和，即：

当a[j][i+2-j]==a[k][n*2-i-k]时f(i,j,k)=f(i-1,j,k)+f(i-1,j-1,k)+f(i-1,j,k+1)+f(i-1,j-1,k+1)，否则f(i,j,k)=0

空间优化

这题数据范围到了500，如果开500^3的数组会MLE

考虑到每次状态转移只需用到f(i-1,j,k)，可以用滚动数组优化空间

因为每次转移只会用到j、j-1、k、k+1，逆序枚举j、正序枚举k即可避免覆盖还未转移的状态。

代码

#include <iostream>

const int M=1000000007; //记得取模

using namespace std;

char a[510][510];
int n,f[510][510],ans;

int main()
{
    int i,j,k;

    cin>>n;

    for (i=1;i<=n;++i)
    {
        for (j=1;j<=n;++j)
        {
            cin>>a[i][j];
        }
    }

    if (a[1][1]==a[n][n]) //若左上角和右下角不同则直接输出0
    {
        f[1][n]=1; //初始化状态，两个点分别在左上角和右下角时方案数为1
        for (i=1;i<=n-1;++i)
        {
            for (j=i+1;j>=1;--j) //逆序枚举j
            {
                for (k=n-i;k<=n;++k) //正序枚举k
                {
                    if (a[j][i+2-j]==a[k][n*2-i-k]) //只有两点所在字母相同时才能转移
                    {
                        f[j][k]=(1ll*f[j][k]+f[j-1][k]+f[j][k+1]+f[j-1][k+1])%M; //1ll*是为了避免爆int，把数组开为long long也可以
                    }
                    else
                    {
                        f[j][k]=0;
                    }
                }
            }
        }

        for (i=1;i<=n;++i)
        {
            ans=(ans+f[i][i])%M; //只有最后到同一点才计入答案
        }
    }

    cout<<ans;

    return 0;
}