本来直接一波状压dpAC的
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
ll dp[50][10];
int path[15][2], p, n, m = 3;void dfs(int l, int now, int pre)
{if(l > m) return;if(l == m){path[p][0] = pre;path[p++][1] = now;return;}dfs(l + 1, (now << 1) | 1, pre << 1);dfs(l + 1, now << 1, (pre << 1) | 1);dfs(l + 2, (now << 2) | 3, (pre << 2) | 3);
}int main()
{dfs(0, 0, 0);while(~scanf("%d", &n) && n != -1){memset(dp, 0, sizeof(dp));dp[0][(1 << m) - 1] = 1;_for(i, 1, n) REP(j, 0, p)dp[i][path[j][1]] += dp[i-1][path[j][0]]; printf("%lld\n", dp[n][(1 << m) - 1]);}return 0;
}然后闲着无聊想用滚动数组优化一下，虽然说对于这道题完全没必要
然后就发现了问题
每次使用的时候要清空这一行的值
因为这道题的状态转移是+=， 以前都是=，所以值可以直接覆盖。
还有一定要i++之后t再改，我一开始是写j++后t就改，然后就连样例都过不了，调了好久才发现
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
ll dp[2][10];
int path[15][2], p, n, m = 3;void dfs(int l, int now, int pre)
{if(l > m) return;if(l == m){path[p][0] = pre;path[p++][1] = now;return;}dfs(l + 1, (now << 1) | 1, pre << 1);dfs(l + 1, now << 1, (pre << 1) | 1);dfs(l + 2, (now << 2) | 3, (pre << 2) | 3);
}int main()
{dfs(0, 0, 0);while(~scanf("%d", &n) && n != -1){memset(dp, 0, sizeof(dp));int t = 0;dp[t][(1 << m) - 1] = 1; t ^= 1;_for(i, 1, n) {REP(j, 0, p) dp[t][path[j][1]] = 0; //这一行是关键 REP(j, 0, p)dp[t][path[j][1]] += dp[t^1][path[j][0]]; t ^= 1;}printf("%lld\n", dp[t^1][(1 << m) - 1]);}return 0;
}