为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。

USACO/rockers

来自NOCOW
跳转到： 导航, 搜索

目录

[编辑] 就是改变的01背包

其实就是01背包的变形

f[i,j]表示1~i物品，使用空间量<=j分钟的最大答案

f[i,j]=max{f[i-1,j], f[i-1,get(a[i],j)]+1};

然后压成1维,a不用记录在数组中

f[j]=max{f[j],f[get(a,j)]+1};

注意j是倒着for的

get函数这么写 （如果可以放得下那么放在这，否则放在前面的CD中） 

 function get(a,j:longint):longint;
 begin 
  if a>t then exit(-1);
  if j mod t<a then exit(j-j mod t-a) else exit(j-a);
 end;

[编辑] 一个提示

就是因为不知道这个，我在看以下题解的时候一头雾水，后来百度了一下，就全部豁然开朗，就把这个提示写在这里了。

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

摘自 http://www.cppblog.com/yuziyu/archive/2009/07/11/89781.html

[编辑] 分析-穷举

一道动态规划题，但观察数据规模，穷举就行了。 穷举每首歌是否选取所有的组合可能(2^20种)，算出每种情况所有光盘上一共能存的歌曲数目，保留最大值即可。

对于穷举每首歌是否选取所有的组合可能，我采用了位运算的高效方法

limit=(1 << N)-1; for (i=0;i<=limit;i++)

然后i对应的每种状况计算能装进光盘中的最大的歌曲数目即可。

--CmYkRgB123 15:30 2008年4月20日 (CST)

[编辑] 分析-动态规划

此题用动态规划做。

A[g,k,r] 表示：在以第g首歌曲开头的序列中(不一定要取第g首歌曲)，还剩下k张CD，且最后一张光盘上还剩下r分钟时间，能取到的最大曲目数。

A[g,k,r]=max{A[g+1,k,r+t[g]](r+t[g]<=l(每张盘的时间),k<n),A[g+1,k+1,t[g]]（t[g]<=l,k<n),A[g+1,k,r]}(g<=m,k<=n)

A[g,k,r]=0(g>m)


By Nickolas Stoudemire Luca Gilardino Aaron KAKA

一个平方复杂度的动态规划，dp[i][j] 记录 在前i个歌曲中选出j个所花费的时间（这里的时间是指 已用了几张CD 和最后一张所剩的时间）

然后目标使每个dp[i][j] 最小， 然后根据j 以及 dp[i][j]记录的时间 确定答案 -------------------复杂度 平方

BY Freefly Cherish ……

[编辑] 分析-双重动态规划

用动态规划很容易的.

1、先利用三重循环计算出每个区间内的在背包重量内的最大值 （利用01背包） 2、再利用三重循环，求解

F[I,J]代表前I个歌曲装在J个唱片的最优值，所以

F[I,J]:=Max{F[K,J]+Maxit[K+1,I]}

3、输出F[N,M]

By 宇智波带鸭子

[编辑] 一个无聊的动规方法

1. 设f[i,j,k]为 前i张光盘中第i张光盘目前录的歌中最靠后的为第j首且第i 张光盘已使用了不超过时间k.第四层循环，枚举l.

2.时间复杂度<O(n*n*m*k) 对于20的数据范围足矣。 

  f[i,j,k]=  f[i,l,k-time[j]]+1{k>=time[j]+time[l]且i<=j时}(1=<l<j)
           f[i,j,k-1]        {time[j]<k<=time[j]+time[l]且i<=j时}
           f[i-1,l,t]+1      {k=time[j]且i<=j时}(1=<l<j)
           f[i-1,j,t]        {i>j时}

....By Crucible library

[编辑] 爆搜者曰

爆搜也过了，最后一个case 0.5s多，见C++。--intheway

我的爆搜case：12 0.2秒过，见C++ ——ABC。

我觉得代码应该是这样： 

    for i:=1 to n do
      for j:=1 to m do
        for k:=1 to t do
        begin
            f[i,j,k]:=f[i,j,k-1];//传递
            f[i,j,k]:=max(f[i,j,k],f[i-1,j,k]); //不取这首曲子
            if a[i]<=k then
            begin
                f[i,j,k]:=max(f[i,j,k],f[i-1,j,k-a[i]]+1); //取这首曲子
                f[i,j,k]:=max(f[i,j,k],f[i-1,j-1,t]+1); //取这首曲子并换个CD
            end;
        end;
Executing...
   Test 1: TEST OK [0.000 secs, 312 KB]
   Test 2: TEST OK [0.000 secs, 312 KB]
   Test 3: TEST OK [0.000 secs, 312 KB]
   Test 4: TEST OK [0.000 secs, 312 KB]
   Test 5: TEST OK [0.000 secs, 312 KB]
   Test 6: TEST OK [0.000 secs, 312 KB]
   Test 7: TEST OK [0.000 secs, 312 KB]
   Test 8: TEST OK [0.000 secs, 312 KB]
   Test 9: TEST OK [0.000 secs, 312 KB]
   Test 10: TEST OK [0.000 secs, 312 KB]
   Test 11: TEST OK [0.000 secs, 312 KB]
   Test 12: TEST OK [0.000 secs, 312 KB]

All tests OK.

应该加一句:f[i,j,k]:=max（f[i,j,k],f[i,j,k-1]）,有背包的思想。

if a[i]=k也应该改为a[i]>k 其实这种方法在空间上可以降一维（见C++代码）

[编辑] 一种时间复杂度O(n^2)的DP算法

设f[i,j](a,b)表示前i首歌曲选取j首歌曲，所消耗的光盘数+最后一张光盘的时间数； 则有f[i,j]可由f[i-1,j]和f[i-1,j-1]两种状态转移而来；找到其中最小的消耗即可； 最后再从n到1枚举答案即可得到结果。时间复杂度O(n^2)。如下图：最大时间也是0.011s 

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 212 KB]
   Test 2: TEST OK [0.011 secs, 212 KB]
   Test 3: TEST OK [0.011 secs, 212 KB]
   Test 4: TEST OK [0.011 secs, 212 KB]
   Test 5: TEST OK [0.000 secs, 212 KB]
   Test 6: TEST OK [0.011 secs, 212 KB]
   Test 7: TEST OK [0.011 secs, 212 KB]
   Test 8: TEST OK [0.000 secs, 212 KB]
   Test 9: TEST OK [0.011 secs, 212 KB]
   Test 10: TEST OK [0.011 secs, 212 KB]
   Test 11: TEST OK [0.000 secs, 212 KB]
   Test 12: TEST OK [0.011 secs, 212 KB]

All tests OK.
Your program ('rockers') produced all correct answers!  This is your
submission #3 for this problem.  Congratulations!

代码详见pascal

BY Skywalker

[编辑] 果断搜索

  Test 1: TEST OK [0.000 secs, 276 KB]
  Test 2: TEST OK [0.000 secs, 276 KB]
  Test 3: TEST OK [0.000 secs, 276 KB]
  Test 4: TEST OK [0.000 secs, 276 KB]
  Test 5: TEST OK [0.000 secs, 276 KB]
  Test 6: TEST OK [0.000 secs, 276 KB]
  Test 7: TEST OK [0.000 secs, 276 KB]
  Test 8: TEST OK [0.000 secs, 276 KB]
  Test 9: TEST OK [0.000 secs, 276 KB]
  Test 10: TEST OK [0.000 secs, 276 KB]
  Test 11: TEST OK [0.000 secs, 276 KB]
  Test 12: TEST OK [0.000 secs, 276 KB]

详见yw100101的pascal代码

[编辑] 枚举+贪心

枚举光盘的位置，每个光盘尽可能的装入到下一个光盘之前的歌曲，由于只考虑数量，贪心即可。先对光盘之间的歌曲按大小排序，然后贪心。（最后多设一个光盘当作边界） 详见liuanxi1的c++代码

[编辑] 二维动规

Test 1: TEST OK [0.000 secs, 276 KB] 

  Test 2: TEST OK [0.000 secs, 276 KB]
  Test 3: TEST OK [0.000 secs, 276 KB]
  Test 4: TEST OK [0.000 secs, 276 KB]
  Test 5: TEST OK [0.000 secs, 276 KB]
  Test 6: TEST OK [0.000 secs, 276 KB]
  Test 7: TEST OK [0.000 secs, 276 KB]
  Test 8: TEST OK [0.000 secs, 276 KB]
  Test 9: TEST OK [0.000 secs, 276 KB]
  Test 10: TEST OK [0.000 secs, 276 KB]
  Test 11: TEST OK [0.000 secs, 276 KB]
  Test 12: TEST OK [0.000 secs, 276 KB]

j是cd数，k是第j张cd所用时间。 

if a[i]<=k
   then begin
        f[j,k]:=max(f[j,k],f[j,k-a[i]]+1);
        f[j,k]:=max(f[j,k],f[j-1,t]+1);
   end;

读者可能会问，f[j,k]:=max(f[j,k],f[j-1,t]+1)是为什么………… 解答很简单，就是： 比如一个光盘剩下5t内存，而你接下来的两首歌的时间是3分钟，4分钟，2分钟，1分钟，1分钟 如果我们想把3分钟和4分钟的刻到光盘，则我们正常的刻录想法就是把3分钟的可进去，剩下两分钟，接着判断2<4于是新开一个光盘，把4分钟的歌放进去，但是我们也可以这样想，既然2分钟的空间用不上，那我们索性大方一点，可以把歌刻在光盘最后面，免得判断，这样并不影响结果，即f[j,5]:=max(f[j,2]+1)；如果不刻4分钟的歌而刻2分钟的歌，那就不能这么大方了，要紧挨着前面的歌刻，为光盘保留最大的空间保证光盘能继续容纳一些歌。 或者也可以这样解释，f[j,t]的所容纳的歌的最大值必须大于或等于f[j,z] 0<=z<t,方面的理解就是既然能f[j,z]那么浪费t-z空间，似的f[j,t]=f[j,z] 解释by CGB

[编辑] 参考代码

C
C++
Pascal
Java

[编辑] 引用

CmYkRgB123 [1] [2]

来自“http://www.nocow.cn/index.php?title=USACO/rockers&oldid=35590”
个人工具