[51nod1503]猪和回文 DP

题解：

　　首先观察到题目要求的是合法回文串的个数，而回文串要求从前往后和从后往前是一样的，因此我们假设有两只猪，分别从左上和右下开始走，走相同的步数最后相遇，那么它们走的路能拼在一起构成一个回文串，当且仅当它们走字符串是完全相同的。

　　那么我们可以根据这个性质进行DP，设f[i][j][k][l]表示第一只猪走到(i, j),第二只猪走到(k, l)的方案数。

　　那么观察到$i + j = k + l$,所以$l$是没必要记录的，因为前面三个确定，l就确定了，然后因为i从1 开始枚举，每次只能走一步，所以只会用到上一步的方案，所以可以滚动一下，这样时空复杂度就都可以承受了。

　　因为要限制两只猪走的步数一样，注意限制第一只猪在红色的三角形中，另一只猪在蓝色的三角形中。

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 510

 #define mod 1000000007

 #define LL long long

 int n, m;

 LL f[][AC][AC], ans;

 char s[AC][AC];

 void pre()

 {

     scanf("%d%d", &n, &m);

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

     if(s[][] != s[n][m]) {printf("0\n"); exit();}

 }

 inline bool check(int i, int j, int k, int l)

 {

     if(i == k && j == l) return true;

     else if(i +  == k && j == l) return true;

     else if(i == k && j +  == l) return true;

     return false;

 }

 void work()

 {

     int l, now = , b = (n + m) / ;

     f[][][n] = ;

     for(R i = ; i <= n; i ++, now ^= )

     {

         for(R j = ; j + i -  <= b; j ++)

         {

             if(i ==  && j == ) continue;

             for(R k = n; k >= i; k --)

             {

                 l = n + m +  - i - j - k;

                 if(l < j || l > m) continue;

                 if(s[i][j] != s[k][l])    continue;

                 f[now][j][k] = f[now ^ ][j][k] + f[now ^ ][j][k + ];

                 f[now][j][k] += f[now][j - ][k] + f[now][j - ][k + ];

                 f[now][j][k] %= mod;

                 if(check(i, j, k, l)) ans += f[now][j][k];

                 if(ans > mod) ans -= mod;

             }

         }

         memset(f[now ^ ], , sizeof(f[now ^ ]));//因为有同层转移，所以要memset，而不能枚举到它的时候再重置

     }

     printf("%lld\n", ans);

 }

 void work1()

 {

     int l, now = , b = (n + m) / ;

     f[][][n] = ;

     for(R i = ; i <= n; i ++, now ^= )

     {

         for(R j = ; j + i -  <= b; j ++)

         {

             if(i ==  && j == ) continue;

             for(R k = n; k >= i; k --)

             {

                 l = n + m +  - i - j - k;

                 if(l < j || l > m) continue;

                 if(s[i][j] != s[k][l])    continue;

                 f[i][j][k] += f[i - ][j][k] + f[i - ][j][k + ];

                 f[i][j][k] += f[i][j - ][k] + f[i][j - ][k + ];

                 f[i][j][k] %= mod;

                 if(check(i, j, k, l)) ans += f[i][j][k];

                 if(ans > mod) ans -= mod;

             }

         }

     }

     printf("%lld\n", ans);

 }

 int main()

 {

 //    freopen("in.in", "r", stdin);

     pre();

     work();

 //    fclose(stdin);

     return ;

 }

巴特西

[51nod1503]猪和回文 DP

最新文章

热门文章