【ybt高效进阶5-5-3】涂抹果酱（轮廓线DP）

涂抹果酱

题目链接：ybt高效进阶5-5-3

题目大意

给你一个矩阵，要你每个位置填上 1/2/3，然后有一行的是固定的。

然后问你要满足任意两个相邻的位置的颜色不同，有多少种方案数。

思路

不难看出是三进制状压 DP。

至于它固定要一个的，那你就以这个作为起点，把问题变成两个（向上和向下）。

这两个的计算方式是一样的，你就看着层数，到了就记录下去。

然后不难想到两边的方案两两组合都可以，所以方案数是乘起来。

然后由于忘了怎么写一整行的状压 DP，就直接写轮廓线 DP 了。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#define mo 1000000

using namespace std;

int n, m, k, three[6], x, st;
int f[2][243], now, nxt;
int ans1, ans2;

int get_wei(int x, int i) {
	return (x / three[i]) % 3;
}

int main() {
	three[0] = 1;
	for (int i = 1; i <= 5; i++) three[i] = three[i - 1] * 3;
	
	scanf("%d %d", &n, &m);
	scanf("%d", &k);
	for (int i = 0; i < m; i++) {
		scanf("%d", &x); x--;
		st += x * three[i];
	}
	
	for (int i = 1; i < m; i++)
		if (get_wei(st, i) == get_wei(st, i - 1)) {
			printf("0"); return 0;
		}
	
	now = 0; nxt = 1;
	f[now][st] = 1;
	for (int i = 1; k + i <= n || k - i >= 1; i++) {
		for (int j = 0; j < m; j++) {
			for (int fr = 0; fr < three[m]; fr++) {
				int to = fr;
				if (get_wei(fr, j) != 0) {//分别是选 0/1/2 三个数字
					if (!j || get_wei(fr, j - 1) != 0) {
						to = to - get_wei(fr, j) * three[j];
						f[nxt][to] = (f[nxt][to] + f[now][fr]) % mo;
					}
				}
				to = fr;
				if (get_wei(fr, j) != 1) {
					if (!j || get_wei(fr, j - 1) != 1) {
						to = to - get_wei(fr, j) * three[j] + three[j];
						f[nxt][to] = (f[nxt][to] + f[now][fr]) % mo;
					}
				}
				to = fr;
				if (get_wei(fr, j) != 2) {
					if (!j || get_wei(fr, j - 1) != 2) {
						to = to - get_wei(fr, j) * three[j] + 2 * three[j];
						f[nxt][to] = (f[nxt][to] + f[now][fr]) % mo;
					}
				}
			}
			
			memset(f[now], 0, sizeof(f[now]));
			now = nxt;
			nxt = now ^ 1;
		}
		
		if (k + i == n) {
			for (int j = 0; j < three[m]; j++)
				ans1 = (ans1 + f[now][j]) % mo;
		}
		if (k - i == 1) {
			for (int j = 0; j < three[m]; j++)
				ans2 = (ans2 + f[now][j]) % mo;
		}
	}
	
	if (k == 1) ans2 = 1;//如果直接就是边界方案数就是 1
	if (k == n) ans1 = 1;
	ans1 = (1ll * ans1 * ans2) % mo;//两边的方案两两组合都可以，所以方案数是乘起来（小心炸 int）
	printf("%d", ans1);
	
	return 0;
}