题目描述

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

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

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

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

一开始我看见这道题打了一道背包……

结果很惨的GG了……

我们设f[n][m][k]表示前n首歌按顺序尽量向m张盘里装,然后附加k分钟所能装的最多歌曲数

那么,显然k<=T,因为……如果k>T那f[i][j][k]等价于f[i][j+1][k-T],所以k>T是没有意义的

我们来考虑第n首歌装到第m+1张盘里的决策,也就是转移f[n][m][k] (因为m张盘外加k分钟,如果用那k分钟,也就是向m+1张里面装)

先初始化一下,也就是尝试放弃第i首歌

 f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);

如果第j+1张盘的前k分钟能装的下,

if (k>=a[i]) f[i][j][k]=max(f[i][j][k],f[i-1][j][k-a[i]]+1);

那就不装,或者用前j张和j+1张的前k-a[i]分钟装前i-1首,第j+1张的最后a[i]分钟(歌曲的长度)装第i首

这两个里面取max

如果第j+1张盘的前k分钟装不下,

else if (j>=1 && t-a[i]>=0) f[i][j][k]=max(f[i][j][k],f[i-1][j-1][t-a[i]]+1);

那么,假如说存在第j张盘(可以有j=0而k>0,也就是装第一张),那么就不装,或者用前j-1张盘外加第j张盘的T-a[i]分钟装前i-1首,用第j张盘装第i首试一下 (那么,就相当于尽量把第i首歌往j整张盘里装,如果a[i]小于T,那一定能装上,而如果T<a[i]了,那这首歌显然只能放弃)。

我们为什么要有第二个方程?原因在于k不一定大于a[i],而如果这首歌对决策有影响,那么T一定大于a[i],所以有必要试着装一下。

那么整个方程……

    for (int i=1;i<=n;i++)
        for (int j=0;j<=m;j++)
            for (int k=0;k<=t;k++)
            {
                f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
                if (k>=a[i]) f[i][j][k]=max(f[i][j][k],f[i-1][j][k-a[i]]+1);
                else if (j>=1 && t-a[i]>=0) f[i][j][k]=max(f[i][j][k],f[i-1][j-1][t-a[i]]+1);
            }

然后这是代码……

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

int n,t,m,a[100]={0};
int f[100][100][100]={0},ans=0;

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=0;j<=m;j++)
            for (int k=0;k<=t;k++)
            {
                f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
                if (k>=a[i]) f[i][j][k]=max(f[i][j][k],f[i-1][j][k-a[i]]+1);
                else if (j>=1 && t-a[i]>=0) f[i][j][k]=max(f[i][j][k],f[i-1][j-1][t-a[i]]+1);
            }
            
    ans=f[n][m][0];
    cout<<ans<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.