NOIP模拟 track
- 这道题看着有字符串就直接想到了字符串匹配
- 我们可以用f[i][j][k]来表示当走到i秒时j高度时已经匹配到第k个的时候的数量
- 我们有这几种转移方式
- 当这一位我们向上时
- 若匹配成功f[i+1][j+1][k+1]+=f[i][j][k]
- 匹配失败就是f[i+1][j-1][0]+=f[i][j][k](注意这里j不能为0)
- 往下走时类似
- 但这样我们会发现太浪费了,而且其中有部分没有计算到
- 我们想到了字符串匹配中当我们失配可以不用回到0,而是上一个相似的地方
- 就如s1=1234123123与s2=123412341234…(省略)匹配时
- 我们在s2中搜到第二个1234时可以不用从0开始,而是直接与s1中的1234连上
- 所以我们只需要再预处理一次即可
- 具体看代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int Max = 205;
int n,f[Max][Max][Max];
char s[Max];
int len,fail[Max][2],nxt[Max];
void Get()
{
int j = 0;
nxt[0] = nxt[1] = 0;
for (int i = 1; i < len; i++)
{
while(j > 0 && s[i] != s[j]) j = nxt[j];
if (s[i] == s[j]) j++;
nxt[i + 1] = j;
}
fail[0][s[0] == 'U'] = 1;
for (int i = 1; i <= len; i++)
{
int pos = i;
while (pos && s[pos] != 'U') pos = nxt[pos];
fail[i][1] = pos + 1;
if (pos == 0 && s[0] == 'D') fail[i][1] = 0;
pos = i;
while (pos && s[pos] != 'D') pos = nxt[pos];
fail[i][0] = pos + 1;
if (pos == 0 && s[0] == 'U') fail[i][0] = 0;
}
return;
}
int main()
{
// freopen("track.in","r",stdin);
// freopen("track.out","w",stdout);
cin >> n;
scanf("%s", s);
len = strlen(s);
if (n&1)
{
printf("0\n");
return 0;
}
Get();
f[0][0][0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= min(i, n-i); j++)
{
for (int k = 0; k < len; k++)
{
if (s[k] == 'U')
{
f[i + 1][j + 1][k + 1] = (f[i + 1][j + 1][k + 1] + f[i][j][k]) % mod;
if (j) f[i + 1][j - 1][fail[k][0]] = (f[i + 1][j - 1][fail[k][0]] + f[i][j][k]) % mod;
}
else
{
f[i + 1][j + 1][fail[k][1]] = (f[i + 1][j + 1][fail[k][1]] + f[i][j][k]) % mod;
if (j) f[i + 1][j - 1][k + 1] = (f[i + 1][j - 1][k + 1] + f[i][j][k]) % mod;
}
}
f[i + 1][j + 1][len] = (f[i + 1][j + 1][len] + f[i][j][len]) % mod;
if (j) f[i + 1][j - 1][len] = (f[i + 1][j - 1][len] + f[i][j][len]) % mod;
}
}
cout << f[n][0][len];
return 0;
}