【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;
}