首页 > 作文

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

更新时间:2023-04-08 21:08:16 阅读: 评论:0

Chess

链接:/d/file/titlepic/showproblem.php /> 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 i1 位就可以有连续的 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=0j10dpi1,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} dpi1,j1,k1 转移过来。并且这第 i i i 位上的传送器传送的目标位置可以是前面 ( i − 1 ) (i-1) (i1) 个位置,所以 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=dpi1,j1,k1java软件工程师简历×(i1)

放上参考的大佬的博客

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);        memt(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]);        el            printf("-1\n");    }    return 0;}

本文地址:https://blog.csdn.net/weixin_44169557/article/details/107642451

本文发布于:2023-04-08 21:08:14,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/zuowen/f052b4fd005e5ddea652b9b410df9fef.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

本文word下载地址:2020 年百度之星·程序设计大赛 – 初赛三 P1005 Chess (HDU 6787) dp.doc

本文 PDF 下载地址:2020 年百度之星·程序设计大赛 – 初赛三 P1005 Chess (HDU 6787) dp.pdf

下一篇:返回列表
标签:传送器   位置   结尾   不放
相关文章
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图