USACO 3.4 Raucous Rockers

Raucous Rockers

You just inherited the rights to N (1 <= N <= 20) previously unreleased songs recorded by the popular group Raucous Rockers. You plan to release a set of M (1 <= M <= 20) compact disks with a selection of these songs. Each disk can hold a maximum of T (1 <= T <= 20) minutes of music, and a song can not overlap from one disk to another.

Since you are a classical music fan and have no way to judge the artistic merits of these songs, you decide on the following criteria for making the selection:

The songs on the set of disks must appear in the order of the dates that they were written.
The total number of songs included will be maximized.

PROGRAM NAME: rockers

INPUT FORMAT

Line 1:	Three integers: N, T, and M.
Line 2:	N integers that are the lengths of the songs ordered by the date they were written.

SAMPLE INPUT (file rockers.in)

4 5 2
4 3 4 2

OUTPUT FORMAT

A single line with an integer that is the number of songs that will fit on M disks.

SAMPLE OUTPUT (file rockers.out)

3

——————————————————————————
一道连我这种蒟蒻都能做出来的dp
dp(i,j)=dp(i-1,k)+packbag(v=t,k+1--j)
【i表示选了几个背包，j表示从前到后选了几首歌】
【然后做一个背包，关于容量为t然后从k+1到j之间选歌】
【背包预处理应该会更快，然而在线处理复杂度够了而且绰绰有余】

 1 /*
 2 ID: ivorysi
 3 PROG: rockers
 4 LANG: C++
 5 */
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 #include <queue>
11 #include <set>
12 #include <vector>
13 #include <string.h>
14 #define siji(i,x,y) for(int i=(x);i<=(y);++i)
15 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
16 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
17 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
18 #define inf 0x3f3f3f3f
19 #define MAXN 400005
20 #define ivorysi
21 #define mo 97797977
22 #define ha 974711
23 #define ba 47
24 #define fi first
25 #define se second
26 #define pii pair<int,int>
27 using namespace std;
28 typedef long long ll;
29 int n,m,t;
30 int song[25];
31 int getso[25][25];
32 int f[25];
33 inline int max(int a,int b){return a>b?a:b;}
34 int check(int b,int e) {
35     if(e<b) return 0;
36     memset(f,0,sizeof(f));
37     siji(i,b,e) {
38         gongzi(j,t,song[i]) {
39             f[j]=max(f[j],f[j-song[i]]+1);
40         }
41     }
42     return f[t];
43 }
44 void solve() {
45     scanf("%d%d%d",&n,&t,&m);
46     siji(i,1,n) scanf("%d",&song[i]);
47     siji(i,1,m) {
48         siji(j,1,n) {
49             xiaosiji(k,0,j) {
50                 getso[i][j]=max(getso[i][j],getso[i-1][k]+check(k+1,j));
51             }
52         }
53     }
54     printf("%d
",getso[m][n]);
55 }
56 int main(int argc, char const *argv[])
57 {
58 #ifdef ivorysi
59     freopen("rockers.in","r",stdin);
60     freopen("rockers.out","w",stdout);
61 #else
62     freopen("f1.in","r",stdin);
63 #endif
64     solve();
65 }