题目描述

难度分:$2600$

输入$n(1 \leq n \leq 50)$和$T(1 \leq T \leq 2500)$，有$n$首歌。

然后输入$n$行，每行两个数$t(1 \leq t \leq 50)$和$g(1 \leq g \leq 3)$，表示第$i$首歌的时长和类型。

你需要从这$n$首歌中选出若干首歌，组成一个播放列表，满足：

1. 总时长为$T$。
2. 没有重复歌曲。
3. 相邻歌曲的类型不同。注意这个列表只播放一次，所以首尾不相邻。

有多少种方案？注意歌曲的顺序不同，也算不同的方案。答案模$10^9+7$。

输入样例$1$

3 3
1 1
1 2
1 3

输出样例$1$

6

输入样例$2$

3 3
1 1
1 1
1 3

输出样例$2$

2

输入样例$3$

4 10
5 3
2 1
3 2
5 1

输出样例$3$

10

算法

动态规划

先不考虑总时长，只考虑相邻歌曲不同的排列方案数。

状态定义

$f[i][j][k][l]$表示$1$、$2$、$3$类型的歌分别有$i$、$j$、$k$首，且以$l$类型的歌结尾的方案数。

状态转移

枚举三首歌的数量，考虑最后一首歌的类型$d$，由于相邻两首歌的类型不同，所以状态转移方程为

$f[i+1][j][k][0]=f[i][j][k][1] + f[i][j][k][2]$
$f[i][j+1][k][1]=f[i][j][k][0] + f[i][j][k][2]$
$f[i][j][k+1][2]=f[i][j][k][0] + f[i][j][k][1]$

给每个状态乘上排列数$i!j!k!$就是每个状态的最终DP值。

然后再考虑时长$T$的限制。$g[i][j][t]$表示第$2$种、第$3$种歌分别选了$i$、$j$首，总时长为$t$的方案数。$h[i][t]$表示第$1$种歌选了时间$t$的方案数。这两个问题都是01背包问题，分别做就行。

如此一来，最后的答案应该就是$i!j!k! \times h[i][t] \times g[j][k][T-t] \times \Sigma_{l=0}^{2}f[i][j][k][l]$累加起来。

复杂度分析

时间复杂度

状态数量为$O(n^3T)$，单次转移的时间复杂度为$O(1)$，因此整个算法的时间复杂度为$O(n^3T)$。

空间复杂度

瓶颈在于$f$、$g$两个DP矩阵。$f$的空间复杂度为$O(n^3)$，$g$的空间复杂度为$O(n^2T)$，因此整个算法的额外空间复杂度为$O(n^3+n^2T)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
constexpr int N = 50 + 5;
constexpr int M = 2500 + 5;
constexpr int MOD = 1e9 + 7;

void add(int &x, int y) {
    x = (x + y) % MOD;
}

int fc[N], f[N][N/2][N/3][3], g[N/2][N/3][M], h[N][M];

int main() {
    int n, T;
    scanf("%d%d", &n, &T);
    // 预处理阶乘
    for(int i = fc[0] = 1; i <= n; i++) {
        fc[i] = 1ll * fc[i - 1] * i % MOD;
    }
    vector<int> a, b, c;
    for(int i = 1; i <= n; i++) {
        int t, g;
        scanf("%d%d", &t, &g);
        if(g == 1) a.push_back(t);
        if(g == 2) b.push_back(t);
        if(g == 3) c.push_back(t);
    }
    if(a.size() < b.size()) swap(a, b);
    if(b.size() < c.size()) swap(b, c);
    if(a.size() < b.size()) swap(a, b);
    int A = a.size(), B = b.size(), C = c.size();
    // f[i][j][k][l]表示三种歌各选了i、j、k首，且最后一首是l
    f[1][0][0][0] = f[0][1][0][1] = f[0][0][1][2] = 1;
    for(int i = 0; i <= A; i++) {
        for(int j = 0; j <= B; j++) {
            for(int k = 0; k <= C; k++) {
                for(int d = 0; d < 3; d++) {
                    // 枚举最后一首歌
                    if(f[i][j][k][d]) {
                        if(d) add(f[i + 1][j][k][0], f[i][j][k][d]);
                        if(d^1) add(f[i][j + 1][k][1], f[i][j][k][d]);
                        if(d^2) add(f[i][j][k + 1][2], f[i][j][k][d]);
                    }
                }
                add(f[i][j][k][0], f[i][j][k][1]);
                add(f[i][j][k][0], f[i][j][k][2]);
                f[i][j][k][0] = 1ll * f[i][j][k][0] * fc[i] % MOD * fc[j] % MOD * fc[k] % MOD;
            }
        }
    }
    g[0][0][0] = 1;
    for(int i = 0; i < B; i++) {
        for(int j = i; j >= 0; j--) {
            for(int p = T - b[i]; p >= 0; p--) {
                add(g[j + 1][0][p + b[i]], g[j][0][p]);
            }
        }
    }
    for(int i = 0; i < C; i++) {
        for(int j = B; j >= 0; j--) {
            for(int k = i; k >= 0; k--) {
                for(int p = T - c[i]; p >= 0; p--) {
                    add(g[j][k + 1][p + c[i]], g[j][k][p]);
                }
            }
        }
    }
    h[0][0] = 1;
    for(int i = 0; i < A; i++) {
        for(int j = i; j >= 0; j--) {
            for(int p = T - a[i]; p >= 0; p--) {
                add(h[j + 1][p + a[i]], h[j][p]);
            }
        }
    }
    int ans = 0;
    for(int j = 0; j <= B; j++) {
        for(int k = 0; k <= C; k++) {
            for(int p = 0; p <= T; p++) {
                if(g[j][k][p]) {
                    for(int i = 0; i <= A; i++) {
                        if(h[i][T - p]) {
                            add(ans, 1ll * f[i][j][k][0] * g[j][k][p] % MOD * h[i][T - p] % MOD);
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}