本来直接一波状压dpAC的
#include#include #include #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#include #include #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;}