USACO rockers – 小溪开大船
你刚刚继承了流行的"破锣摇滚"乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲，发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐，一首歌不能分装在两张CD中。
不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：
1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注：第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)
2.选中的歌曲数目尽可能地多。
INPUT FORMAT:
(file rockers.in)
第一行： 三个整数：N, T, M.
第二行： N个整数，分别表示每首歌的长度，按创作时间顺序排列。
OUTPUT FORMAT:
(file rockers.out)
一个整数，表示可以装进M张CD盘的乐曲的最大数目。
Read full article from USACO rockers – 小溪开大船
你刚刚继承了流行的"破锣摇滚"乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲，发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐，一首歌不能分装在两张CD中。
不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：
1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注：第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)
2.选中的歌曲数目尽可能地多。
格式
PROGRAM NAME: rockersINPUT FORMAT:
(file rockers.in)
第一行： 三个整数：N, T, M.
第二行： N个整数，分别表示每首歌的长度，按创作时间顺序排列。
OUTPUT FORMAT:
(file rockers.out)
一个整数，表示可以装进M张CD盘的乐曲的最大数目。
SAMPLE INPUT
SAMPLE OUTPUT
此题是很经典的01背包问题变种，需要你对01背包解法做一些变通，这类型的题目有很多，比如有N个抽屉，需要放入M个物品等等，以后遇到这种题目就不怕不怕啦。。。。
int n, t, m;
int songs[20]; // 每首歌曲的长度
// 递归穷搜
// value为目前为止累积刻录的歌曲数量，sindex表示第i首歌，bindex表示第i张光盘，remain表示当前光盘容量
int fill(int value, int sindex, int bindex, int remain)
{
if(sindex >= n || bindex >= m)
return value;
// 容量是否充足
bool enough = remain >= songs[sindex];
return std::max(fill(value, sindex + 1, bindex, remain),
enough ?
fill(value + 1, sindex + 1, bindex, remain - songs[sindex])
: fill(value, sindex, bindex + 1, t));
}
// 非递归穷搜
int search()
{
int max = 0;
unsigned int mark = 1;
unsigned int mark_max = 1 << n;
// mark的2进制位代表第i张歌曲是否需要拷入cd
for (; mark < mark_max; mark += 1)
{
int value = 0;
int index = 0;
int remain = t;
int i = 0;
for(; i < n; ++i)
{
if (mark & (1 << i))
{
if(songs[i] > t)
break;
if(remain >= songs[i])
{
remain -= songs[i];
value += 1;
}
else
{
index += 1;
if(index >= m)
break;
remain = t - songs[i];
value += 1;
}
}
}
if (i == n && max < value)
max = value;
}
return max;
}
int jump(int v, int j)
{
if(v > j) return -1;
return (j % t - v) >= 0 ? (j - v) : (j / t * t - v);
}
// 01背包的解法
// 此解法的难度在于如何在容量不足时换碟
// 技巧在于，把背包容量看成m*t大小，划分成m块，每次去判断单个块容量是否够放，如果不够则跳到下一个块
// 这样我们的背包公式可表示为
// f[i][j] = max(f[i-1][j], f[i-1][jump(songs[i], j)] + 1)
// i为第i首歌曲，j为容量，songs[i]表示为歌曲需要消耗的容量，jump函数为跳转到相应的容量位置，
// f[i][j]则表示前i个物品容量小于等于j时的最优解
// 降维打击后可变为1维，公式就不列了
int package01()
{
int values[20*20 + 1] = {0};
for(int i = 0; i < n; ++i)
{
for(int j = m*t; j >= songs[i]; --j)
{
int index = jump(songs[i], j);
values[j] = std::max(values[j], index >= 0 ? values[index]+1 : 0);
if(i == n - 1) break;
}
}
return values[m*t];
}
int main()
{
ifstream fin("rockers.in");
ofstream fout("rockers.out");
fin >> n >> t >> m;
for(int i = 0; i < n; ++i)
{
fin >> songs[i];
}
// 递归穷搜超时
// fout << fill(0, 0, 0, t);
// 非递归穷搜通过
// fout << search() << endl;
// 01背包最快最经典
fout << package01() << endl;
return 0;
}
