思路自西瓜and大佬博客：https://www.cnblogs.com/henry-1202/p/10590327.html#_label3
数据范围小 可直接dp
f[i][j][a][b] 表示 i位置上是j i-1上是a i-2上是b
状态转移是由i-1转移过来的，所以就必须还要一个i-3 所以就多加上一个循环
最主要就是转移过程中要枚举每种情况 然后排除掉
大佬的博客用了map和string简化了枚举的过程
不过他说只有六种情况 我布吉岛为啥只有六种 我写出了八种qaq
map<int, string> mp; bool check(int a, int b, int c, int d) { if (mp[a] + mp[b] + mp[c] == "AGC") return 0; if (mp[a] + mp[c] + mp[b] == "AGC") return 0; if (mp[a] + mp[b] + mp[d] == "AGC") return 0; if (mp[a] + mp[c] + mp[d] == "AGC") return 0; if (mp[b] + mp[a] + mp[c] == "AGC") return 0; if (mp[b] + mp[c] + mp[d] == "AGC") return 0; if (mp[b] + mp[d] + mp[c] == "AGC") return 0; if (mp[c] + mp[b] + mp[d] == "AGC") return 0; return 1; }
mp[0]=‘E‘就是来处理刚开始未到3个字符时候的情况 不过枚举j也就是第i个位置的字符就从1开始了 所以之后的不会受到mp[0]的影响了
#include <cstdio> #include <algorithm> #include <string> #include <map> using namespace std; map<int, string> mp; long long f[110][5][5][5]; const long long mod = 1e9 + 7; bool check(int a, int b, int c, int d) { if (mp[a] + mp[b] + mp[c] == "AGC") return 0; if (mp[a] + mp[c] + mp[b] == "AGC") return 0; if (mp[a] + mp[b] + mp[d] == "AGC") return 0; if (mp[a] + mp[c] + mp[d] == "AGC") return 0; if (mp[b] + mp[a] + mp[c] == "AGC") return 0; if (mp[b] + mp[c] + mp[d] == "AGC") return 0; if (mp[b] + mp[d] + mp[c] == "AGC") return 0; if (mp[c] + mp[b] + mp[d] == "AGC") return 0; return 1; } int main() { int n; scanf("%d", &n); f[0][0][0][0] = 1; mp[0] = ‘E‘, mp[1] = ‘A‘, mp[2] = ‘C‘, mp[3] = ‘G‘, mp[4] = ‘T‘; for (int i = 1; i <= n; i++) for (int j = 1; j <= 4; j++) for (int a = 0; a <= 4; a++) for (int b = 0; b <= 4; b++) for (int l = 0; l <= 4; l++) if (check(l, b, a, j)) f[i][j][a][b] = (f[i][j][a][b] + f[i-1][a][b][l]) % mod; long long ans = 0; for (int i = 1; i <= 4; i++) for (int j = 1; j <= 4; j++) for (int k = 1; k <= 4; k++) ans = (ans + f[n][i][j][k]) % mod; printf("%lld\n", ans); return 0; }
AtCoder Beginner Contest 122 D - We Like AGC(DP)
原文：https://www.cnblogs.com/Mrzdtz220/p/10604839.html
