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之间选歌】
【背包预处理应该会更快，然而在线处理复杂度够了而且绰绰有余】
/*
ID: ivorysi
PROG: rockers
LANG: C++
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <string.h>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
#define inf 0x3f3f3f3f
#define MAXN 400005
#define ivorysi
#define mo 97797977
#define ha 974711
#define ba 47
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
typedef long long ll;
int n,m,t;
int song[];
int getso[][];
int f[];
inline int max(int a,int b){return a>b?a:b;}
int check(int b,int e) {
if(e<b) return ;
memset(f,,sizeof(f));
siji(i,b,e) {
gongzi(j,t,song[i]) {
f[j]=max(f[j],f[j-song[i]]+);
}
}
return f[t];
}
void solve() {
scanf("%d%d%d",&n,&t,&m);
siji(i,,n) scanf("%d",&song[i]);
siji(i,,m) {
siji(j,,n) {
xiaosiji(k,,j) {
getso[i][j]=max(getso[i][j],getso[i-][k]+check(k+,j));
}
}
}
printf("%d\n",getso[m][n]);
}
int main(int argc, char const *argv[])
{
#ifdef ivorysi
freopen("rockers.in","r",stdin);
freopen("rockers.out","w",stdout);
#else
freopen("f1.in","r",stdin);
#endif
solve();
}