题解 P7822【「RdOI R3」学习算法】
SfumatoCannon_
·
·
题解
0.吐槽
赛事想出来的做法，当时觉得这题挺简单的（倒是代码实现上调了好久）
比完赛一看题解，？？怎么个个都这么复杂，又是压维又是滚动数组的（甚至让我一度怀疑数据过水）
下面，我就介绍一种做法，理解起来很自然，优化起来也很容易。
1.题意解释
有一个长度为 n 的序列，其中包含的数字范围为从 1 到 m.
规定数字 i 最多只能连续出现 a_i 次。
求满足上述要求的序列一共有多少中，答案对 10^9+7 取模。
2.解题思路
我们发现，这道题目的核心在于 “规定数字 i 最多只能连续出现 a_i 次” 这个限制条件。
我们不妨思考一下：如果我们按照线性动态规划的方式，一个一个地往表格里填数字，当我填到第 i 个数字的时候，和它关系最大的是什么？没错，是第 i-1 个数字。
如果第 i-1 个数字和第 i 个数字不一样的话，那么第 i 个数字填下去，一定是合法的。
否则呢？设当时填的数字为 j ，如果第 i-1 个数字和第 i 个数字是一样的，且 a_j> i-1 的话，我们仍然可以放心大胆地填下去，因为填下去之后，连续出现的数字是不可能超过 a_j 个的（因为本身就只有 a_j 个数字啊）。
那么，如果第 i-1 个数字和第 i 个数字是一样的，且 a_j\leq i-1 的时候呢？那么在前面 i-1 个数字构成的组合里，就不可避免地会出现一种情况，它由恰好 a_j 个 j 结尾，当且仅当这种情况时，第 i 个数字不能填成 j.那么，我们怎么计算这种非法情况的方案数呢？
我们知道，在这种情况下，我们要填的数是第 i 个数，而且从第 i-a_j 个数到第 i-1 个数全部都是 j. 那么问题来了：第 i-a_j-1 个数是几呢？没错，只要不是 j 就行了！
而且我们还可以知道，这种情况下，第 i-a_j 个数到第 i-1 个数全都是固定死的，真正对非法方案数产生贡献的，只有前面的 i-a_j-1 个数。也就是说，“填到第 i-a_j-1 个数且不是以 j 结尾” 的方案数总和，等于 “填到第 i-1 个数，且从 i-a_j 到 i-1 全部都是 j 的方案数”。好好思考一下上面这句话！
所以，第 i-1 个数字等于第 i 个数字时的合法方案总数
$=$ (前面 $i-1$ 个数字构成的合法方案总数) $-$ (前面 $i-a_j-1$ 个数字构成的不是以 $j$ 结尾的方案数总和).
现在我们知道了第 $i-1$ 个数字不等于第 $i$ 个数字时的合法方案总数，也知道了他们相等时的合法方案总数，那么把它们加起来，就知道了我们要求的方案数。
想到了以上这些，状态转移式子就很好推了。我们设 $dp[i][j]$ 表示当前填到第 $i$ 个数，且结尾数字是 $j$ 的合法方案总数，那么必然有：
$$dp[i][j]=\sum_{k=1,k\not=j}^{m}dp[i-1][k]+(dp[i-1][j]-\sum_{k=1,k\not=j}^{m}dp[i-a[j]-1][k])$$
$$=\sum_{k=1}^{m}dp[i-1][k]-\sum_{k=1,k\not=j}^{m}dp[i-a[j]-1][k].$$
这种做法是 $O(n^3)$ 的，拿不到满分，但我们可以很容易观察出，式子里面的 $\sum_{k=1}^{m}$ 是可以预处理出来的。
设 $sum[i]=\sum\limits_{k=1}^{m}dp[i][k]$ ,于是式子转化为：
$$dp[i][j]=sum[i-1]-(sum[i-a[j]-1]-dp[i-a[j]-1][j]).$$
转化成了 $O(n^2)$ 的，于是这道题就可做了。
至于滚动数组什么的？不需要！只要不用 ```long long``` 就可以卡过去。
另外在代码实现上，我们还需要注意之前说过的 $a_j>i-1$ 的情况，并予以特判。
还有一个地方需要特判：那就是当 $m=1$ 且唯一的 $a[1]<n$ 的时候，这种情况下是不可能填完的，应输出```0```。（对于其余的情况，可以证明是肯定存在解的，```12121212...```地填即可）
***
### 3.Code
```cpp
#include <cstdio>
typedef long long ll;
#define MODNUM 1000000007
#define MAXN 7001
ll n, m;
unsigned int dp[MAXN][MAXN];
ll sum[MAXN];
ll a[MAXN];
int main()
{
ll i, j, k;
scanf("%lld%lld", &n, &m);
for (i = 1; i <= m; i++)
scanf("%lld", &a[i]);
if (m == 1 && a[1] < n)
{
printf("0");
return 0;
}
for (i = 1; i <= m; i++)
dp[1][i] = 1;
sum[1] = m;
for (i = 2; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
dp[i][j] = sum[i - 1];
if (i > a[j])
{
if (i == a[j] + 1)
dp[i][j] = (dp[i][j] - 1 + MODNUM) % MODNUM;
else
dp[i][j] = (dp[i][j] - (sum[i - a[j] - 1] - dp[i - a[j] - 1][j]) + MODNUM) % MODNUM;
}
}
for (j = 1; j <= m; j++)
sum[i] = (sum[i] + dp[i][j]) % MODNUM;
}
printf("%lld", sum[n]);
return 0;
}
```