京东9.17笔试第三题
简单dp,dp[i][a][b][k]表示i位的字符串，第i位为a，第i-1位为b，之前是否已经含有red（k为1表示有，0表示无） 的方案数，可以使用滚动数组优化掉第一维度
时间复杂度为 n*26*26*26*2，会t掉。故需要优化，可以考虑对字母进行压缩，分别用0，1，2，3来表示字母 r,e,d,其他字母 。这样时间复杂度可以降为n*4*4*4*2 ，具体转移方程可以看代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int mod = 1e9 + 7;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<vector<vector<int>>> dp(5, vector<vector<int>>(5, vector<int>(2, 0)));
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
dp[i][j][0] = (i == 3 ? 23 : 1) * (j == 3 ? 23 : 1);
// R,E,D,$
for (int i = 2; i < n; i++){
vector<vector<vector<int>>> rdp(5, vector<vector<int>>(5, vector<int>(2, 0)));
for (int c = 0; c < 4; c++)
for (int b = 0; b < 4; b++)
for (int a = 0; a < 4; a++){
if (c == 2 && b == 1 && a == 0)//der不转移
continue;
rdp[a][b][(c == 0 && b == 1 && a == 2) ? 1 : 0] += dp[b][c][0] * (a == 3 ? 23 : 1);
rdp[a][b][1] += dp[b][c][1] * (a == 3 ? 23 : 1);
rdp[a][b][0] %= mod, rdp[a][b][1] %= mod;
}
dp = rdp;
}
int ans = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
ans += dp[i][j][1], ans %= mod;
cout << ans << endl;
}
查看7道真题和解析