Codeforces 570E - Pig and Palindromes - [滚动优化DP]

题目链接:https://codeforces.com/problemset/problem/570/E

题意:

给出 $n \times m$ 的网格,每一格上有一个小写字母,现在从 $(1,1)$ 位置走到 $(n,m)$ 位置,要求经过路径构成一个回文串。

要求走路方向保证坐标不会减小(即只能往下或者往右走),要求你给出路径方案数目。

题解:

考虑 $f[x_1][y_1][x_2][y_2]$ 表示一端从 $(1,1)$ 出发,走到了 $(x_1,y_1)$,同时另一端从 $(n,m)$ 出发,走到了 $(x_2,y_2)$,此时形成回文串的数目。

这个是不难维护的,主要问题是这个维数过多,开不下。然后不难发现,如果用 $f[step][x_1][x_2]$ 来维护,可以通过步数 $step$ 和 $x$ 算出 $y$,

然后更进一步可以发现 $step$ 不需要全部维护,可以使用滚动优化。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+;
const int SIZE=; int n,m;
char mp[SIZE][SIZE];
ll f[][SIZE][SIZE]; inline bool In(int x,int y)
{
return <=x && x<=n && <=y && y<=m;
}
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++) scanf("%s",mp[i]+); int now=;
memset(f[now],,sizeof(f[now]));
f[now][][n]=(ll)(mp[][]==mp[n][m]);
for(int step=;step<=(n+m)/-;step++)
{
now^=;
memset(f[now],,sizeof(f[now]));
for(int x1=;x1<=n;x1++)
{
for(int x2=n;x2>=;x2--)
{
int y1=step+-x1, y2=n+m-step-x2;
if(!In(x1,y1) || !In(x2,y2)) continue;
if(mp[x1][y1]!=mp[x2][y2]) continue; f[now][x1][x2]+=f[now^][x1][x2];
f[now][x1][x2]%=mod; f[now][x1][x2]+=f[now^][x1-][x2+];
f[now][x1][x2]%=mod; f[now][x1][x2]+=f[now^][x1-][x2];
f[now][x1][x2]%=mod; f[now][x1][x2]+=f[now^][x1][x2+];
f[now][x1][x2]%=mod;
}
}
} ll ans=;
if((n+m)%)
{
for(int i=;i<=n;i++) ans+=f[now][i][i], ans%=mod;
for(int i=;i<n;i++) ans+=f[now][i][i+], ans%=mod;
}
else
{
for(int i=;i<=n;i++) ans+=f[now][i][i], ans%=mod;
}
cout<<ans<<endl;
}
上一篇:The Non-Inverting Amplifier Output Resistance by Adrian S. Nastase [转载]


下一篇:生成war的jdk版本高于tomcat使用的jdk版本,导致项目不能正常被访问