题目描述
贝西想从奶牛摇滚乐队的 N 首歌里挑出一些录制一套专辑。专辑分 K 张唱片，每张唱片可容纳总长为 C 分钟的歌曲。第 i 首歌的长度为 T i 分钟，录制唱片时，唱片之间的歌曲需要保持原本的顺序。第一张唱片里的歌必须排在第二张唱片前面，之后的每张唱片里也是如此。同时，每首歌曲必须完整地放 在一张唱片里，不然，就只能舍去不录了。请问贝西应该选哪些歌曲，才能让专辑里装下的歌曲尽量多？
输入
第一行：三个整数 N，C 和 K，1 ≤ N ≤ 100,1 ≤ C ≤ 1000,1 ≤ K ≤ 1000
• 第二行到第 N + 1 行：第 i + 1 行有一个整数 T i ，1 ≤ T i ≤ 1000
输出
单个整数：表示可以装进专辑的歌曲数目
样例输入
4 5 2 4 3 4 2
样例输出
3
提示
第一张唱片装第一首歌，第二张唱片装第二首和第四首歌
题解：
背包问题,F[i][j]表示前i个唱片，第i张用了j分钟最大能录制的唱片
F[i][j]=max(F[i-1][t],F[i][j-a[i]])+1
F[i-1][t]表示将这首歌直接放进第i个唱片开始的位置
F[i][j-a[i]]表示将这首歌插入在该唱片已有的几个唱片后面.
复杂度有点超,不能乱搞,但是数据并没有卡
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int N=1005; 8 int a[N],F[N][N]; 9 int main() 10 { 11 int n,t,m; 12 scanf("%d%d%d",&n,&t,&m); 13 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 14 for(int i=1;i<=n;i++) 15 { 16 for(int j=m;j>=1;j--) 17 { 18 for(int k=t;k>=a[i];k--)F[j][k]=max(F[j-1][t],F[j][k-a[i]])+1; 19 } 20 } 21 printf("%d",F[m][t]); 22 return 0; 23 }