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
dpi,j)=dpi-1,k)+packbagv=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 sijii,x,y) forint i=x);i<=y);++i)
15 #define gongzij,x,y) forint j=x);j>=y);--j)
16 #define xiaosijii,x,y) forint i=x);i<y);++i)
17 #define sigongzij,x,y) forint 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 maxint a,int b){return a>b?a:b;}
34 int checkint b,int e) {
35     ife<b) return 0;
36     memsetf,0,sizeoff));
37     sijii,b,e) {
38         gongzij,t,song[i]) {
39             f[j]=maxf[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     sijii,1,n) scanf"%d",&song[i]);
47     sijii,1,m) {
48         sijij,1,n) {
49             xiaosijik,0,j) {
50                 getso[i][j]=maxgetso[i][j],getso[i-1][k]+checkk+1,j));
51             }
52         }
53     }
54     printf"%d
",getso[m][n]);
55 }
56 int mainint 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 }