自动搬运

查看原文

来自洛谷，原作者为

	zxh_mc DETERMINATION

搬运于2025-08-24 22:42:42，当前版本为作者最后更新于2022-11-25 20:10:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路比较简单的一道题。

用的五维 dp，看到二维和三维的 dp 直接膜了 orz。

正文开始。

分析

不难看出 dp。

因为 $b_i$ 的值只与 $a_{i-1},a_i,a_{i+1}$ 有关，所以我们定义 $b_i$ 被 $a_{c_1},a_{c_2},...a_{c_p}$ 满足为在这些 $a$ 中最大的一项恰好为 $b_i$。

用 $dp_{i,j,0/1,0/1,z}$ 来表示此状态下的方案数。

其中：

• $i$ 表示当前处于第 $i$ 项。
• $j$ 表示当前这一项选择 $j$。
• $1/0$ 表示 $b_i$ 是否被 $a_{i-1},a_i$ 满足。
• $1/0$ 表示 $b_0$ 是否被 $a_0,a_1$ 满足。
• $z$ 表示 $a_0$ 选择 $z$。

显然，$a_i$ 的最大值就是 $\min(b_{i-1},b_i,b_{i+1})$，又因为 $b_i\le10$，所以 $a_i$ 的最大值也是 $10$。

状态转移方程比较复杂。

如果 $i>1$，那么我们需要枚举 $a_i$ 和 $a_{i-1}$。

这时候存在两种情况：

1. $b_i$ 被 $a_i,a_{i-1}$ 满足，此时应该更新 $dp_{..,..,1,..,..}$ 的值。
2. $b_i$ 不被 $a_i,a_{i-1}$ 满足，此时应该更新 $dp_{..,..,0,..,..}$ 的值。

注意：在选择 $a_i$ 的时候，$b_{i-1}$ 必须被 $a_{i-2},a_{i-1},a_i$ 满足，原因显然。

但当 $i=1$ 时，应该单独讨论，因为 $a_1$ 的选择会影响到 dp 数组的第 $4$ 项，而 $i\ge2$ 则不会。思路跟 $i\ge2$ 的情况类似，不再赘述。

最后统计答案时，我们有几种情况：

• $dp_{n-1,x,1,1,y}$，因为此时 $b_{n-1}$ 和 $b_0$ 已经被满足，而其它的 $b$ 也都被满足，直接加上即可。
• $dp_{n-1,x,0,1,y}$ 当 $b_{n-1}\le y$ 时可以相加，因为 $a$ 数组是环形的。
• $dp_{n-1,x,1,0,y}$ 当 $b_0\le x$ 时可以相加，原因同上。

最后，记得取模。

AC Code

臭长臭长的代码 qwq。

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
const int MOD = 1e9 + 7;

int n;
int dp[N][11][2][2][11], b[N], am[N];
int st;

inline int nxt (int idx) {
	return ((idx + 1) % n);
}

inline int pre (int idx) {
	return ((idx - 1 + n) % n);
}

int m (int x) {
	if (x < MOD) return x;
	return x - MOD;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 0;i < n;i++) cin >> b[i];
	for (int i = 0;i < n;i++) am[i] = min(b[pre(i)], min(b[i], b[nxt(i)]));
	for (int i = 0;i <= am[0];i++) if (i < b[0]) dp[0][i][0][0][i] = 1; else dp[0][i][1][1][i] = 1;
	for (int x = 0;x <= am[0];x++) for (int st = 0;st <= 1;st++) for (int j = 0;j <= am[1];j++) {
		if (j < b[1] && x < b[1]) {
			if (j < b[0]) dp[1][j][0][st][x] += m(dp[0][x][0][st][x] + dp[0][x][1][st][x]), dp[1][j][0][st][x] = m(dp[1][j][0][st][x]);
			else dp[1][j][0][1][x] += m(dp[0][x][0][st][x] + dp[0][x][1][st][x]), dp[1][j][0][1][x] = m(dp[1][j][0][1][x]);
		}
		else {
			if (j < b[0]) dp[1][j][1][st][x] += m(dp[0][x][0][st][x] + dp[0][x][1][st][x]), dp[1][j][1][st][x] = m(dp[1][j][1][st][x]);
			else dp[1][j][1][1][x] += m(dp[0][x][0][st][x] + dp[0][x][1][st][x]), dp[1][j][1][1][x] = m(dp[1][j][1][1][x]);
		}
	}
	for (int i = 2;i < n;i++) {
		int p = i - 1;
		for (int x = 0;x <= am[0];x++) for (int st = 0;st <= 1;st++) {
			for (int j = 0;j <= am[i];j++) {
				for (int z = 0;z <= am[p];z++) {
					if (j < b[i] && z < b[i]) {
						if (j < b[p]) dp[i][j][0][st][x] += dp[p][z][1][st][x];else dp[i][j][0][st][x] += m(dp[p][z][0][st][x] + dp[p][z][1][st][x]);
						dp[i][j][0][st][x] = m(dp[i][j][0][st][x]);
					}
					else {
						if (j < b[p]) dp[i][j][1][st][x] += dp[p][z][1][st][x];
						else dp[i][j][1][st][x] += m(dp[p][z][0][st][x] + dp[p][z][1][st][x]);
						dp[i][j][1][st][x] = m(dp[i][j][1][st][x]);
					}
				}
			}
		}
	}
	int ans = 0;
	for (int x = 0;x <= am[0];x++) for (int i = 0;i <= am[n - 1];i++) {
		ans += dp[n - 1][i][1][1][x]; ans = m(ans);
		if (i >= b[0]) ans += dp[n - 1][i][1][0][x];
		if (x >= b[n - 1]) ans += dp[n - 1][i][0][1][x];
		ans = m(ans);
	}
	cout << ans << endl;
	return 0;
}