常见的网站首页布局有哪几种,php学校网站系统,网站开发公司选择,宝安中心医院是什么级别文章目录1. 题目2. 解题1. 题目
链接#xff1a;https://ac.nowcoder.com/acm/contest/9715/C 来源#xff1a;牛客网
音游狂热爱好者牛牛接到了一个新的任务#xff0c;那就是给一张乐谱设计重音符。每当玩家敲击重音符的时候就会发出bang的美妙声音!!
每一…
文章目录1. 题目2. 解题1. 题目
链接https://ac.nowcoder.com/acm/contest/9715/C 来源牛客网
音游狂热爱好者牛牛接到了一个新的任务那就是给一张乐谱设计重音符。每当玩家敲击重音符的时候就会发出bang的美妙声音!!
每一张乐谱都有n个音符从左到右一字排开现在牛牛的任务就是选出其中m个音符将其标记为重音符同时任意两个重音符之间都必须隔着至少k个音符。
一个有意思的问题诞生了请求出这样合法的设计方案种数并输出答案对1000000007取模的结果。
示例1
输入
3,2,1
返回值
1备注:
2. 解题
dp[pos][time] 表示在位置 pos 时第 time 次的方案数
class Solution {
public:/*** * param n int整型 乐谱总音符数* param m int整型 重音符数* param k int整型 重音符之间至少的间隔* return long长整型*/typedef long long ll;long long solve_bangbang(int n, int m, int k) {// write code hereif(m 0) return 1;int mod 1e97;vectorvectorll dp(n, vectorll(m1, 0));for(int i 0; i n; i)dp[i][1] 1;for(int t 2; t m; t){for(int i 0; i n; i){if(dp[i][t-1] 0)continue;for(int j ik1; j n; j){dp[j][t] dp[i][t-1];dp[j][t] (dp[j][t]%mod);}}}ll ans 0;for(int i 0; i n; i)ans (ansdp[i][m])%mod;return ans;}
};227ms
class Solution {
public:/*** * param n int整型 乐谱总音符数* param m int整型 重音符数* param k int整型 重音符之间至少的间隔* return long长整型*/typedef long long ll;long long solve_bangbang(int n, int m, int k) {// write code hereif(m 0) return 1;int mod 1e97;vectorvectorll dp(n, vectorll(m1, 0));for(int i 0; i n; i)dp[i][1] 1;for(int i 1; i n; i){if(i-k-1 0)for(int t 1; t m; t){dp[i][t1] dp[i-k-1][t];}for(int t 1; t m; t){dp[i][t] dp[i-1][t];dp[i][t] % mod;}}return dp[n-1][m];}
};4ms 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
