题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^3)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,t,m;
int f[21][21][21];//三维中第一维是因为一首歌只能选1次
//指选到i,第j个唱片,用了k个时间的最多唱片个数
int main()
{
cin>>n>>t>>m;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
for(int j=0;j<=m;j++)
for(int k=0;k<=t;k++)
{
f[i][j][k]=f[i-1][j][k];
if(a<=k&&j>=1)//小心越界,还有j为0时不能执行18行,不然一张唱片没有也会有歌
{
f[i][j][k]=max(f[i][j][k],f[i-1][j][k-a]+1);
f[i][j][k]=max(f[i][j][k],f[i-1][j-1][t]+1);//f[i-1][j-1][t]中t是因为19行中f[i-1][j][k-a]+1可以浪费时间
//相当于唱片开始不放,过一会再开始放
}
}
}
cout<<f[n][m][t];
return 0;
}