loj#10172 涂抹果酱 (状压DP)

题目：

#10172. 「一本通 5.4 练习 1」涂抹果酱

解析：

三进制的状压DP

经过简单的打表发现，在\(m=5\)时最多有\(48\)种合法状态

然后就向二进制一样枚举当前状态和上一层的状态进行转移就好了

由于第\(k\)行是给定的，所以转移时要特判一下第\(k\)行，并且注意下一\(k=1\)的情况

设\(f[i][j]\)表示第\(i\)行\(j\)状态时的方案数

\(f[i][j] += f[i - 1][k],k是上一行的状态\)

代码：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 10;

const int mod = 1e6;

int n, m, k, num, sum = 1, sta, kk, ans;

/*

	sum为状态上节

	sta是第k行状态

	num是合法状态数

*/

int state[N], f[10010][50];

//state记录状态

//f[i][j]表示dp 到第i行j状态的方案数

bool check(int x) {		//判断状态是否合法

	int len = 0;

	int b[10];

	while (x) b[++len] = x % 3, x /= 3;

	if (len < m - 1) return 0;

	for (int i = 2; i <= len; ++i) if (b[i] == b[i - 1]) return 0;

	return 1;

}

bool cmp(int x, int y) {	//判断两个状态是否可以相邻

	for (int i = 1; i <= m; ++i) {

		if ((x % 3) == (y % 3)) return 0;

		x /= 3, y /= 3;

	}

	return 1;

}

signed main() {

	cin >> n >> m >> k;

	for (int i = 1, x; i <= m; ++i) cin >> x, kk = kk * 3 + x - 1;

	for (int i = 1; i <= m; ++i) sum *= 3;

	for (int i = 0; i < sum; ++i) if (check(i)) {

			state[++num] = i;

			if (i == kk) sta = num;

		}

	if (sta == 0) {

		cout << 0;

		return 0;

	}

	for (int i = 1; i <= n; ++i) {

		if (i == k) {

			if (i == 1) f[1][sta] = 1;

			else for (int j = 1; j <= num; ++j)

					if (cmp(state[sta], state[j]))

						(f[i][sta] += f[i - 1][j]) %= mod;

		} else {

			if (i == 1) for (int j = 1; j <= num; ++j) f[i][j] = 1;

			else for (int j = 1; j <= num; ++j)

					for (int pre = 1; pre <= num; ++pre)

						if (cmp(state[j], state[pre]))

							(f[i][j] += f[i - 1][pre]) %= mod;

		}

	}

	for (int i = 1; i <= num; ++i) (ans += f[n][i]) %= mod;

	cout << ans;

}