文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

鏈接：https://ac.nowcoder.com/acm/contest/9715/C
來源：牛客網(wǎng)

音游狂熱愛好者牛牛接到了一個(gè)新的任務(wù)，那就是給一張樂譜設(shè)計(jì)重音符。每當(dāng)玩家敲擊重音符的時(shí)候就會發(fā)出"bang"的美妙聲音!!

每一張樂譜都有n個(gè)音符從左到右一字排開，現(xiàn)在牛牛的任務(wù)就是選出其中m個(gè)音符將其標(biāo)記為重音符，同時(shí)任意兩個(gè)重音符之間都必須隔著至少k個(gè)音符。

一個(gè)有意思的問題誕生了，請求出這樣合法的設(shè)計(jì)方案種數(shù)，并輸出答案對1000000007取模的結(jié)果。

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

備注:

2. 解題

• dp[pos][time] 表示在位置 pos 時(shí)，第 time 次的方案數(shù)

class Solution { public:/*** * @param n int整型 樂譜總音符數(shù)* @param m int整型 重音符數(shù)* @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 = 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

class Solution { public:/*** * @param n int整型 樂譜總音符數(shù)* @param m int整型 重音符數(shù)* @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 = 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

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的牛客 Bang! Bang!（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。