思路比较简单的一道题。
用的五维 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}\)。
这时候存在两种情况：
- \(b_i\) 被 \(a_i,a_{i-1}\) 满足，此时应该更新 \(dp_{..,..,1,..,..}\) 的值。
- \(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;
}