上海计算机学会2024年3月月赛C++乙组T4录制唱片
发布时间
阅读量：
阅读量
录制唱片
内存限制: 256 Mb时间限制: 1000 ms
题目描述
乐队有 N 部作品，编号为 1 到 N，其中第 i 首歌的长度为 Ti 分钟。小爱想从中精选一些歌曲，把歌录到唱片里，然后出版一套专辑。这套专辑最多可以有 K 张唱片。
每张唱片里可以录多首歌，但它们的总长不能超过 C 分钟。每首歌必须完整地放在一张唱片里，一首歌不能分割成两段放在两张唱片里，此外，录制唱片的时候，还要注意保持歌曲的编号顺序。
假设小爱选录编号为 1,3,5 的歌曲，她不能把 1,5 放在第一张唱片里，而把 3 放在第二场唱片里，因为 3 的编号比 5 更小。
考虑到这些要求之后，请问小爱应该选择录制哪些歌曲，才能让出版的专辑收入尽量多的歌曲？
输入格式
- 第一行：三个整数 N，C 和 K
- 第二行到第N+1行：在第 i+1 行有一个整数 Ti
输出格式
- 单个整数：表示可以装进专辑的歌曲数目
数据范围
- 1≤N≤1000
- 1≤C≤10000
- 1≤K≤10000
- 1≤Ti≤10000
样例数据
输入:
4 5 2
4
3
4
2
输出:
3
解析：动态规划，详见代码：
#include <bits/stdc++.h>
using namespace std;
int n,c,k;
int t[1005];
int dp[1005][1005];//dp[i][j]表示i张唱片前j个歌曲最多可以装几个
int b[1005][1005];//b[i][j]表示从i到j一张唱片最多可以装几个歌曲
int cnt=0;//歌曲总量
priority_queue <int> q;//大根堆
int main() {
cin>>n>>c>>k;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x<=c){//只保留长度小于c的歌曲
cnt++;
t[cnt]=x;
}
}
if (k>=cnt){//如果唱片数超过歌曲数，可以全收录
cout<<cnt;
return 0;
}
//预处理b数组
for(int i=1;i<=cnt;i++){//枚举开始歌曲
int sum=0;//队列中歌曲总长度
int num=0;//队列中歌曲数量
while(!q.empty()) q.pop();//清空队列
for(int j=i;j<=cnt;j++){//枚举结束歌曲
q.push(t[j]);//入队
sum+=t[j];//计算总长度
num++;//增加数量
if (sum>c){//若超长
sum-=q.top();//去掉最长的
q.pop();//最长歌曲出队
num--;//数量更新
}
b[i][j]=num;//保存数量
}
}
for(int i=1;i<=k;i++){//枚举K张唱片
for(int j=i;j<=cnt;j++){//限定j首歌曲
if(i>=j){
dp[i][j]=j;
}else{
for(int l=j;l>=i;l--){//区间dp，取l为分界点，l到j一张唱片
dp[i][j]=max(dp[i][j],b[l][j]+dp[i-1][l-1]);
}
}
}
}
cout<<dp[k][cnt];
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~