洛谷 P2736 “破锣摇滚”乐队 Raucous Rockers 题解【搜索】【动态规划】

作者: wjyyy 分类: DP,搜索,解题报告 发布时间: 2018-07-05 15:03

点击量:23

 

   数据范围比较小,可以搜索,不过也有0ms的背包做法。

 

题目描述

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

 

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

 

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

 

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

 

输入输出格式

输入格式:

第一行: 三个整数:N, T, M。

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

 

输出格式:

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

 

输入输出样例

输入样例#1:
4 5 2
4 3 4 2
输出样例#1:
3

说明

题目翻译来自NOCOW。

USACO Training Section 3.4

 

题解:

   对于每首音乐来说,可以被正序装到每个CD中,我们可以通过搜索,找出每首音乐可能放在哪个CD中,统计最优答案。时间复杂度为\(2^n\),可以完成,注意细节就可以了。

 

   我们可以将每个CD当做一个背包,每次让后面的背包0状态继承前面背包的装东西状态的最大值,就可以实现多背包的DP了,时间复杂度为\(n^3\)。

 

   对拍的时候发现std(DP)写错了3次,bf(搜索)错了2次。。。

 

Code of SEARCH:

#include<cstdio>
#include<cstring>
int l[22];
int n,t,m;
int sum=0,ans=0;
void dfs(int cd,int num,int tmp)//num表示现在应该选哪个了
{
    ans=ans>sum?ans:sum;
    if(num>n)
        return;
    for(int i=num;i<=n;i++)
        if(l[i]+tmp<=t)
        {
            sum++;
            dfs(cd,i+1,l[i]+tmp);
            sum--;
        }
    if(cd==m)
        return;
    for(int i=num;i<=n;i++)
        if(l[i]<=t)
        {
            sum++;
            dfs(cd+1,i+1,l[i]);
            sum--;
        }
    return;
}
int main()
{
    scanf("%d%d%d",&n,&t,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&l[i]);
    for(int i=1;i<=n;i++)
        if(l[i]<=t)
        {
            sum=1;
            dfs(1,i+1,l[i]);
        }
    printf("%d\n",ans);
    return 0;
}

 

Code of DP:

#include<cstdio>
#include<cstring>
int max(int x,int y)
{
    return x>y?x:y;
}
int min(int x,int y)
{
    return x<y?x:y;
}
int f[22][22];
int l[22];
int main()
{
    //freopen("data.in","r",stdin);
    //freopen("std.out","w",stdout);
    memset(f,0,sizeof(f));
    int n,m,t;
    scanf("%d%d%d",&n,&t,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&l[i]);
    //开始背包 填表
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=min(n,min(i,m));j>=1;j--)
            for(int k=0;k<=t;k++)//防止当前状态不合法而跳过
                f[j][0]=max(f[j-1][k],f[j][0]);
        for(int j=min(n,min(i,m));j>=1;j--)
        {
            for(int k=t;k>=l[i];k--)
            {
                f[j][k]=max(f[j-1][k-l[i]]+1,max(f[j][k],f[j][k-l[i]]+1));
                if(f[j][k]>ans)
                    ans=f[j][k];
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */