一開(kāi)始把題意理解錯(cuò)了，以為刻在同一張光盤(pán)上的歌曲的時(shí)間順序不變就可以了。
事實(shí)上不僅同光盤(pán)上的歌曲寫(xiě)入時(shí)間要按順序，前一張光盤(pán)上的歌曲不能比后一張歌曲寫(xiě)入時(shí)間要晚。
數(shù)據(jù)量比較少，用回溯法，dp也行。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("rockers.in");
ofstream?fout("rockers.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
int?capacity[20];;
int?songs[20];
int?song_num,disk_num;
int?res?=?0;
int?cur;
void?backtracing(int?depth,int?last)
{
????if(depth==song_num){
????????if(cur>res){
????????????res?=?cur;
????????}
????????return;
????}
???
??? //如果后面所有的歌曲都加上還比最優(yōu)值小，剪枝
????if(cur+song_num-depth<=res)
???????return;?
????for(int?i=last;i<disk_num;++i){
???????? //如果當(dāng)前歌曲需要刻錄，那只需刻在第一張能裝得下的光盤(pán)上。
????????if(?capacity[i]>=songs[depth]){
????????????cur++;
????????????capacity[i]-=songs[depth];
????????????backtracing(depth+1,i);
????????????capacity[i]+=songs[depth];
????????????cur--;
????????????break;
????????}
????}
??? // 不刻當(dāng)前歌曲
????backtracing(depth+1,last);
}
void?solve()
{
????int?c;
????in>>song_num>>c>>disk_num;
????for(int?i=0;i<song_num;++i)
????????in>>songs[i];
????for(int?i=0;i<disk_num;++i)
????????capacity[i]?=?c;
????backtracing(0,0);
????out<<res<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}