小y的容器[dp]

tag：

• 滚动dp 容斥
• cf分段2100+

题意简单讲一下：

给三个容器，往里面填数字
其中容器内任意连续的两个数字之差不得大于3
例如[1,2,5]合法而[1,2,6]不合法。
且存在数字不能装进指定容器中
求解方案数

我们通过连续三个数字之差不得大于三这个点作为突破口，猜测方案为计数dp

因此我们令每个容器都只保留最后存在的数字，就可以知道下一个数字是否能填入当前这个容器中。这里的状态就用dp状态方程转移即可。

因此突破口就变成了如何记录下容器留下的最后数字。这里我们立马想到滚动dp。这里就是滚动dp的一种表现形式。我们仅需要知道这个数字距离当前数字差了几位即可。最大相差超过4就脱离了题目的行列，我们就没必要让他继续脱离下去了。只需要都记录在4这个状态里就行。

 dp[1][1][j+1][k+1] += dp[0][i][j][k]
 dp[1][i][1][k+1] += dp[0][i][j][k]
 dp[1][i][j+1][1] += dp[0][i][j][k]

这样就能解决当i，j，k是1234的所有情况。 特殊情况当i，j，k是0时，就不变。0的情况就是此时一个数也没有填进去 1就是当前这个数字就是填在三个容器中的第几维度。2就是容器内最大的数字与当前数字差1 至于最后就是维护整个dp可以再开一维转移，也可以直接滚动数组。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m;
ll dp[10][10][10];
int ck[20000][5];
const int mod = 1e9 + 7;
auto add(ll &a, const ll &b) {
	a = (a + b) % mod;
	return a;
}
auto up(int k) {
	if (k == 0 || k == 4)return k;
	else return k + 1;
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		ck[a][b] = 1;
	}
	int kksk = n;
	dp[0][0][0] = 1;
	for(int tmp = 1 ; tmp <= n ; tmp++){
		ll res[5][5][5] = {};
		for (int i = 0; i <= 4; i++) {
			for (int j = 0; j <= 4; j++) {
				for (int k = 0; k <= 4; k++) {
					if (!ck[tmp][1]&&i!=4)add(res[1][up(j)][up(k)], dp[i][j][k]);
					if (!ck[tmp][2]&&j!=4)add(res[up(i)][1][up(k)], dp[i][j][k]);
					if (!ck[tmp][3]&&k!=4)add(res[up(i)][up(j)][1], dp[i][j][k]);
				}
			}
		}
		for (int i = 0; i <= 4; i++) {
			for (int j = 0; j <= 4; j++) {
				for (int k = 0; k <= 4; k++) {
					dp[i][j][k] = res[i][j][k];
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 1; k <= 4; k++) {
				add(ans,dp[i][j][k]);
			}
		}
	}
	cout << ans << "\n";
	//for(int i = 0 ; i < )
}