1391. 喧嚣摇滚乐队

二维费用背包。

状态表示：

(f(i,j,k))：从前(i)首歌曲中选，当前已使用的唱片数为(j)，且当前唱片的总时长不超过(k)的情况下，能够选出的歌曲数的最大值。

状态转移：

[f(i,j,k)=egin{cases} f(i-1,j,k) & 不选第i首歌曲 \ f(i-1,j.k-v_i)+1 & 将第i首歌曲加入当前唱片 \ f(i-1,j-1,t)+1 & 将第i首歌曲加入新唱片 end{cases} ]

(t)为每张唱片歌曲总时长的最大限制。

边界：

[f(0,0,0 sim t) = 0 ]

const int N = 25;
int f[N][N];
int n, m, t;

int main()
{
    cin >> n >> t >> m;

    for(int i = 1; i <= n; i++)
    {
        int v;
        cin >> v;
        for(int j = m; j >= 1; j--)
            for(int k = t; k >= v; k--)
                f[j][k] = max(f[j][k], max(f[j][k - v] + 1, f[j - 1][t] + 1));
    }

    cout << f[m][t] << endl;
    //system("pause");
    return 0;
}