P2736 “破锣摇滚”乐队 Raucous Rockers

题目描述

你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的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：复制

说明

题目翻译来自NOCOW。

USACO Training Section 3.4

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=;

int n,T,m;

int a[N];

int dp[N][N];

int main()

{

    scanf("%d%d%d",&n,&T,&m);

    for(int i=;i<=n;++i)

        scanf("%d",a+i);

    for(int i=;i<=n;++i)

    {

        for(int j=m;j>=;--j)

        {

            for(int k=T;k>=a[i];--k)

            {

                dp[j][k]=max(dp[j][k],max(dp[j-][T]+,dp[j][k-a[i]]+));

            }

        }

    }

    printf("%d",dp[m][T]);

    return ;

}

DP版

/*每一首歌都有三种状态。 1、在当前盘里装 2、换张盘装 3、不装    那我们对每首歌进行三种状态的dfs，选到最后找出最大值，且这样做第i张盘的最后一首歌一定比第i+1张盘的第一张早，因为dfs中的歌的编号是递增的*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int n,m,t,ans=-,tot=;

int cd[],tim[];

void dfs(int now,int sum)    //now表示当前选到了第几首歌，sum表示选了几首歌

{

    if(sum+n+-now<=ans) return;    //重要剪枝，如果把后面的歌全装上也不能使答案更新，那么在往下一定不会有更优解，则return

    if(now==n+)    //歌选完了

    {

        ans=max(ans,sum);

        return;

    }

    if(cd[tot]>=tim[now])        //在当前盘里装

    {

        cd[tot]-=tim[now];

        dfs(now+,sum+);

        cd[tot]+=tim[now];

    }

    if(tot<m&&t>=tim[now])        //换张盘装

    {

        tot++;

        cd[tot]-=tim[now];

        dfs(now+,sum+);

        cd[tot]+=tim[now];

        tot--;

    }

    dfs(now+,sum);        //不装

}

int main()

{

    scanf("%d%d%d",&n,&t,&m);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&tim[i]);

    }

    for(int i=;i<=m;i++)

    {

        cd[i]=t;

    }

    dfs(,);

    printf("%d",ans);

    return ;

}

DFS版

巴特西

P2736 “破锣摇滚”乐队 Raucous Rockers

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章