SRM531 Div1 Easy NoRepeatPlaylist

2016/04/20 (Wed) SRM DP

問題

音楽が $N$ 曲入ったスマホと $P$ 曲聞く時間がある。 $P$ 曲からなるプレイリスト (曲の列) を以下の条件を満たすように作る。

  • $N$ 曲全て使う
  • 隣り合う $M$ 曲に同じものがない

ありうるものは何通か。

方針

「$dp(i,j) = $ $i$ 曲目までに $j$ 曲使って作るプレイリストは何通りか」とおいて解く。 漸化式はソースコードを見てください。

1番目の式はまだ聞いたことがない曲を使う場合。そのようなものは $N-j$ 曲ある。

2番目の式は既に使った曲を再利用する場合。 直近の $M$ 曲は使えないので $j-M$ 通りある。

DP 難しい… こんな簡単な漸化式かつ練習会で一度見ていたのに思いつくまですごく時間がかかった。

包除原理でも解けるらしい。

実装

#include <bits/stdc++.h>
 namespace std;
using ll = long long;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(c) begin(c), end(c)

static const int mod = 1000000007;
ll dp[111][111];

#define add(x,y) ((x += y) %= mod)

class NoRepeatPlaylist {
public:
    int N;
    int M;
    int P;
    int numPlaylists(int _N, int _M, int _P) {
        this->N = _N;
        this->M = _M;
        this->P = _P;
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for(int i = 0; i < P; ++i){ // from i-th music
            for(int j = 0; j <= min(N,i); ++j){
                add(dp[i+1][j+1], dp[i][j] * (N-j)); // use new
                if(j >= M){
                    add(dp[i+1][j], dp[i][j] * (j-M)); // reuse
                }
            }
        }

        return dp[P][N];
    }
};