poj 2663 Tri Tiling （状压dp+多米诺骨牌问题+滚动数组反思）

本来直接一波状压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;

}