欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2020 年百度之星·程序设计大赛 - 初赛三 P1005 Chess (HDU 6787) dp

程序员文章站 2022-06-22 19:29:04
Chess链接:http://acm.hdu.edu.cn/showproblem.php?pid=6787solution不能出现连续的11个传送器,其他情况一定都可以到达点n。dpi,j,kdp_{i,j,k}dpi,j,k​ 表示前 iii 个位置,已经放了 kkk 个传送器,且以 iii 结尾的连续的传送器有 jjj 个。考虑第 iii 位放或者不放,如果不放,那么就会从这个位置断开,以 iii 结尾的连续的传送器就变成了0,那么第 i−1i-1i−1 位就可以有连续的 0~10 个...

Chess

2020 年百度之星·程序设计大赛 - 初赛三 P1005 Chess (HDU 6787) dp
链接:http://acm.hdu.edu.cn/showproblem.php?pid=6787

solution

不能出现连续的11个传送器,其他情况一定都可以到达点n。
dpi,j,kdp_{i,j,k} 表示前 ii 个位置,已经放了 kk 个传送器,且以 ii 结尾的连续的传送器有 jj 个。
考虑第 ii或者不放
如果不放
那么就会从这个位置断开,以 ii 结尾的连续的传送器就变成了0,那么第 i1i-1 位就可以有连续的 0~10 个传送器,所以 dpi,0,k=0j10dpi1,j,kdp_{i,0,k} = \sum_{0\le j \le 10}dp_{i-1,j,k}
如果
那么 dpi,j,kdp_{i,j,k} 就应该从 dpi1,j1,k1dp_{i-1,j-1,k-1} 转移过来。并且这第 ii 位上的传送器传送的目标位置可以是前面 (i1)(i-1) 个位置,所以 dpi,j,k=dpi1,j1,k1×(i1)dp_{i,j,k}=dp_{i-1,j-1,k-1} \times (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

相关标签: 动态规划