USACO Raucous Rockers

这道题的正解是三维的动态规划，和背包问题很相似。本人起初也想到了背包，不过只写了个二维的，因此一直没有通过。但是，由于N的最大值只有20，并且要计算某个情况下可以收入的歌曲数非常容易的（贪心算法）。因此本人使用了枚举，用一个long型表示几个歌曲的选择情况，再用test函数计算可以收入的歌曲数量。

为什么要使用三维动态规划呢？如果仅仅用max[i][j]表示第i个光盘占用前j分钟可以装下的歌曲数量，就无法体现题目的一个约束条件“The songs on the set of disks must appear in the order of the dates that they were written.”，因此不具有最优子结构性质，因此还要增加第三维k，用来表示最后一个专辑的编号。

实测表明动态规划算法在时间上明显优于枚举算法。

使用枚举算法的代码：

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MXN 23
05
06 long base[MXN];
07 int N,T,M;
08 int len[MXN];
09
10 int test(long state)
11 {
12     int i,c;
13     int t,d;
14     for(i = c = t = d = 0;i < N && d < M;i ++)
15     {
16         if(state & base[i])        //add this song
17         {
18             if(len[i] + t <= T)
19             {
20                 t += len[i];
21                 c ++;
22             }
23             else if(d < M - 1)
24             {
25                 t = len[i];
26                 d ++;
27                 c ++;
28             }
29             else break;
30         }
31     }
32     //printf("%d\n",c);
33     return c;
34 }
35
36 void calc_base()
37 {
38     int i;
39     base[0] = 1;
40     for(i = 1;i < MXN;i ++)
41         base[i] = base[i - 1] << 1;
42 }
43
44 int get_max(int a,int b)
45 {
46     if(a > b)    return a;
47     return b;
48 }
49
50 int main()
51 {
52     freopen("rockers.in","r",stdin);
53     freopen("rockers.out","w",stdout);
54     scanf("%d%d%d",&N,&T,&M);
55     long i;
56     int ans;
57     for(i = 0;i < N;)
58     {
59         scanf("%d",&len[i]);
60         if(len[i] <= T)    i ++;
61         else N --;
62     }
63     calc_base();
64     for(i = ans = 0;i < base[N];i ++)
65     {
66         ans = get_max(test(i),ans);
67     }
68     printf("%d\n",ans);
69     fclose(stdin);
70     fclose(stdout);
71     return 0;
72 }

使用动态规划的代码

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MXN 22
05
06 int len[MXN];
07 int N,T,M;
08 int max[MXN][MXN][MXN];
09
10 void solve()
11 {
12     int i,j,k,v;
13     for(i = 0;i < MXN;i ++)
14     for(j = 0;j < MXN;j ++)
15     for(k = 0;k < MXN;k ++)
16         max[i][j][k] = -1;
17     max[1][0][0] = 0;
18     for(i = 1;i <= M;i ++)
19         for(j = 0;j <= T;j ++)
20             for(k = 0;k <= N;k ++)
21             {
22                 //printf("disc:%d time:%d last:%d max:%d\n",i,j,k,max[i][j][k]);
23                 if(max[i][j][k] != -1)
24                     for(v = k + 1;v <= N;v ++)
25                     {
26                         if(j + len[v] <= T)
27                         {
28                             if(max[i][j][k] + 1 > max[i][j + len[v]][v])    max[i][j + len[v]][v] = max[i][j][k] + 1;
29                         }
30                         else
31                         {
32                             if(max[i][j][k] + 1 > max[i + 1][len[v]][v])    max[i + 1][len[v]][v] = max[i][j][k] + 1;
33                         }
34                     }
35             }
36 }
37
38 void output()
39 {
40     int ans = 0;
41     int i,j,k;
42     for(i = 1;i <= M;i ++)
43         for(j = 1;j <= T;j ++)
44             for(k = 1;k <= N;k ++)
45                 if(max[i][j][k] > ans)    ans = max[i][j][k];
46     printf("%d\n",ans);
47 }
48
49 int main()
50 {
51     freopen("rockers.in","r",stdin);
52     freopen("rockers.out","w",stdout);
53     scanf("%d%d%d",&N,&T,&M);
54     int i;
55     for(i = 1;i <= N;)
56     {
57         scanf("%d",&len[i]);
58         if(len[i] <= T)    i ++;
59         else N --;
60     }
61     if(N == 0)
62     {
63         printf("0\n");
64         return 0;
65     }
66     solve();
67     output();
68     fclose(stdin);
69     fclose(stdout);
70     return 0;
71 }