首页 > 牛客编程巅峰赛S2第6场 - 钻石&王者T2
头像
余夕Yuel
编辑于 2020-12-05 09:17
+ 关注

牛客编程巅峰赛S2第6场 - 钻石&王者T2

dp
class Solution {
public:
    /**
     * 
     * @param n int整型 乐谱总音符数
     * @param m int整型 重音符数
     * @param k int整型 重音符之间至少的间隔
     * @return long长整型
     */
    const long long mod = 1e9 + 7;
    long long a[1010][1010], f[1010];
    long long solve_bangbang(int n, int m, int k) {
        if (m == 0)
            return 1;
        a[0][0] = 1;
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++)
                f[j] = (f[j] + a[max(i - k - 1, 0)][j]) % mod;
            for (int j = 1; j <= m; j++)
                a[i][j] = (a[i][j] + f[j - 1]) % mod;
        }
        long long ans = 0;
        for (int i = 1; i <= n; i++)
            ans = (ans + a[i][m]) % mod;
        return ans;
    }
};


全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

近期精华帖

热门推荐