Chess
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6787
solution
不能出现连续的11个传送器，其他情况一定都可以到达点n。
d p i , j , k dp_{i,j,k} dpi,j,k 表示前 i i i 个位置，已经放了 k k k 个传送器，且以 i i i 结尾的连续的传送器有 j j j 个。
考虑第 i i i 位放或者不放，
如果不放，
那么就会从这个位置断开，以 i i i 结尾的连续的传送器就变成了0，那么第 i − 1 i-1 i−1 位就可以有连续的 0~10 个传送器，所以 d p i , 0 , k = ∑ 0 ≤ j ≤ 10 d p i − 1 , j , k dp_{i,0,k} = \sum_{0\le j \le 10}dp_{i-1,j,k} dpi,0,k=∑0≤j≤10dpi−1,j,k。
如果放，
那么 d p i , j , k dp_{i,j,k} dpi,j,k 就应该从 d p i − 1 , j − 1 , k − 1 dp_{i-1,j-1,k-1} dpi−1,j−1,k−1 转移过来。并且这第 i i i 位上的传送器传送的目标位置可以是前面 ( i − 1 ) (i-1) (i−1) 个位置，所以 d p i , j , k = d p i − 1 , j − 1 , k − 1 × ( i − 1 ) dp_{i,j,k}=dp_{i-1,j-1,k-1} \times (i-1) dpi,j,k=dpi−1,j−1,k−1×(i−1) 。
放上参考的大佬的博客
code
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int dp[1005][11][1005]; // dp[i,j,k] 代表 以i结尾连续的传送器有j个，当前已经放了k个
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n, m;
scanf("%d%d", &n, &m);
memset(dp, 0, sizeof(dp));
dp[1][0][0] = 1;
for (int i = 2; i <= n; i++)
{
for (int k = 0; k <= m; k++)
{
// 当前位置i不放，那么第i-1位上连续0个~10个的都满足此情况
for (int j = 0; j <= 10; j++)
{
// 也就是 在已经放了k个的情况下，以i结尾连续0个传送器 的方案数
dp[i][0][k] = (dp[i][0][k] + dp[i - 1][j][k]) % mod;
}
if (i != n) // 位置n不能放
{
// 当前位置i放，就要更新以i结尾连续j个的情况，因为第i位上放了，所以最小连续是1
for (int j = 1; j <= 10; j++)
{
// k>=1 是因为第i位放上后，当前已经放的个数就>=1了，前i-1个要放的就是k-1>=0即k>=1
if (k >= 1)
{
// *(i-1)是因为i位置上的传送器可到达的地方可以是前面(i-1)个位置
dp[i][j][k] = (dp[i][j][k] + 1LL * dp[i - 1][j - 1][k - 1] * (i - 1) % mod) % mod;
}
}
}
}
}
if (dp[n][0][m])
printf("%d\n", dp[n][0][m]);
else
printf("-1\n");
}
return 0;
}
本文地址：https://blog.csdn.net/weixin_44169557/article/details/107642451
