牛客 Bang! Bang!（动态规划）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

链接：https://ac.nowcoder.com/acm/contest/9715/C 来源：牛客网

音游狂热爱好者牛牛接到了一个新的任务，那就是给一张乐谱设计重音符。每当玩家敲击重音符的时候就会发出"bang"的美妙声音!!

每一张乐谱都有n个音符从左到右一字排开，现在牛牛的任务就是选出其中m个音符将其标记为重音符，同时任意两个重音符之间都必须隔着至少k个音符。

一个有意思的问题诞生了，请求出这样合法的设计方案种数，并输出答案对1000000007取模的结果。

代码语言：javascript复制

示例1
输入
3,2,1
返回值
1

备注:

2. 解题

• dp[pos][time] 表示在位置 pos 时，第 time 次的方案数

代码语言：javascript复制

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 here
        if(m == 0) return 1;
        int mod = 1e9 7;
        vector<vector<ll>> dp(n, vector<ll>(m 1, 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 = i k 1; 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 = (ans dp[i][m])%mod;
        return ans;
    }
};

227ms

代码语言：javascript复制

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 here
        if(m == 0) return 1;
        int mod = 1e9 7;
        vector<vector<ll>> dp(n, vector<ll>(m 1, 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][t 1] = 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

---

dp time

0 人点赞