洛谷P2736 “破锣摇滚”乐队 Raucous Rockers

题目描述

你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲，发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐，一首歌不能分装在两张CD中。

不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：

1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注：第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)

2.选中的歌曲数目尽可能地多

输入输出格式

输入格式：

第一行：三个整数：N, T, M.

第二行： N个整数，分别表示每首歌的长度，按创作时间顺序排列。

输出格式：

一个整数，表示可以装进M张CD盘的乐曲的最大数目。

输入输出样例

输入样例#1：

4 5 2
4 3 4 2

输出样例#1：

说明

题目翻译来自NOCOW。

USACO Training Section 3.4

题目大意：m首歌，n个cd，每首歌有时间，然后每个cd最多放的时间是t，必须按顺序放入cd,最多能放几首歌。

题解1：

dfs 每一首歌的状态是放入当前cd，放入下一个cd，不放入cd。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,t,m,ans,tot=1,tim[22],cd[22];

void dfs(int now,int sum){    
    if(n-now+1+sum<=ans)return;
    if(now==n+1){
        ans=max(ans,sum);
        return;
    }
    if(tim[now]<=cd[tot]){
        cd[tot]-=tim[now];
        dfs(now+1,sum+1);
        cd[tot]+=tim[now];
    }
    if(tot<m&&t>=tim[now]){
        tot++;
        cd[tot]-=tim[now];
        dfs(now+1,sum+1);
        cd[tot]+=tim[now];
        tot--;
    }
    dfs(now+1,sum);
}
int main(){
    scanf("%d%d%d",&n,&t,&m);
    for(int i=1;i<=n;i++)scanf("%d",&tim[i]);
    for(int i=1;i<=m;i++)cd[i]=t;
    dfs(1,0);
    printf("%d
",ans);
    return 0;
}

题解2：

参考洛谷物是人非...

f[i]表示时间i能装的最多的唱片的数量，答案为f[t*m],为了避免唱片被分割的情况，

如果tim[k]<=i%t,如果第k个唱片时间小于残缺的长篇的时间则加入，否则加入完整的唱片。

#include<iostream>
#include<cstdio>
using namespace std;
int t,m,n,a[22],f[500];
int main(){
    scanf("%d%d%d",&n,&t,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=t*m;j>=1;j--){
            if(a[i]<=j%t)f[j]=max(f[j],f[j-a[i]]+1);
            else
            if(a[i]<=j/t*t)
            f[j]=max(f[j],f[j/t*t-a[i]]+1);
        }
    }
    cout<<f[t*m];
    return 0;
}

题解3：f[i][j]表示前i张唱片，第i张唱片的时间为j的最大值。

by shenben

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define N 22
int n,m,t,v[N],f[N][N];//f[k][j] k张CD,第k张CD的容量为j的最大数量 
int main(){
    scanf("%d%d%d",&n,&t,&m);
    for(int i=1;i<=n;i++) scanf("%d",&v[i]);
    for(int i=1;i<=n;i++){
        for(int k=m;k;k--){
            for(int j=t;j>=v[i];j--){
                f[k][j]=max(f[k][j],max(f[k-1][t],f[k][j-v[i]])+1);
            }
        }
    }
    printf("%d",f[m][t]);
    return 0;
}