USACO-Section3.4 Raucous Rockers【动态规划】

本文主要是介绍USACO-Section3.4 Raucous Rockers【动态规划】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲，发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐，一首歌不能分装在两张CD中。

不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：

1.歌曲必须按照创作的时间顺序在CD盘上出现。
2.选中的歌曲数目尽可能地多。
3.不仅同光盘上的歌曲写入时间要按顺序，前一张光盘上的歌曲不能比后一张歌曲写入时间要晚。

INPUT FORMAT:

第一行：三个整数：N, T, M.

第二行： N个整数，分别表示每首歌的长度，按创作时间顺序排列。

OUTPUT FORMAT:

一个整数，表示可以装进M张CD盘的乐曲的最大数目。

SAMPLE INPUT
4 5 2
4 3 4 2

SAMPLE OUTPUT
3

解题思路：

这道题据说最少的时间复杂度为O(n^2),我用的方法复杂度为O(M * N ^ 2 ),dp[i][j][k]代表从i到j首歌曲用k张CD最多可保存的歌曲数，具体思想为先通过优先队列计算dp[i][j][1]，然后通过四边形动规，dp[i][j][k]=max(dp[i][j][k],dp[i][pro][k-1]+dp[j+1][j][1])解决。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<algorithm>
#define INF 99999999
using namespace std;
FILE *fin,*fout;
int N,T,M;
int dp[25][25][25];//从i-j用k张CD最多可保存的歌曲数 
int data[25];
int init(int a){int sum=T;priority_queue<int> q;q.push(0);for(int i=a;i<N;i++){if(sum>=data[i]){sum-=data[i];q.push(data[i]);}else if(data[i]<q.top()){sum=sum+(q.top()-data[i]);q.pop();q.push(data[i]);}dp[a][i][1]=q.size()-1;}
} 
int main(){fin  = fopen ("rockers.in", "r");fout = fopen ("rockers.out", "w");fscanf(fin,"%d%d%d",&N,&T,&M);for(int i=0;i<N;i++)fscanf(fin,"%d",&data[i]); for(int i=0;i<N;i++){init(i); }for(int k=2;k<=M;k++){for(int temp=0;temp<N;temp++)for(int i=0;i<N-temp;i++){int j=i+temp;if(i==j)dp[i][j][k]=dp[i][j][k-1];for(int pro=i;pro<j;pro++){dp[i][j][k]=max(dp[i][j][k],dp[i][pro][k-1]+dp[pro+1][j][1]);}}}fprintf(fout,"%d\n",dp[0][N-1][M]);exit(0);
}