USACO 3.4 Raucous Rockers


一开始把题意理解错了,以为刻在同一张光盘上的歌曲的时间顺序不变就可以了。
事实上不仅同光盘上的歌曲写入时间要按顺序,前一张光盘上的歌曲不能比后一张歌曲写入时间要晚。

数据量比较少,用回溯法,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;
    }
   
    //如果后面所有的歌曲都加上还比最优值小,剪枝
    
if(cur+song_num-depth<=res)
       
return

    
for(int i=last;i<disk_num;++i){
         //如果当前歌曲需要刻录,那只需刻在第一张能装得下的光盘上。
        
if( capacity[i]>=songs[depth]){
            cur
++;
            capacity[i]
-=songs[depth];
            backtracing(depth
+1,i);
            capacity[i]
+=songs[depth];
            cur
--;
            
break;
        }
    }

    // 不刻当前歌曲
    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;
}


posted on 2009-07-11 11:48 YZY 阅读(1410) 评论(0)  编辑 收藏 引用 所属分类: AlgorithmUSACO回溯法搜索


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜