USACO 3.4.4 Raucous Rockers

其实由于此题数据范围过小，穷举的状态数不超过2^20=1048576，完全可以接受。

DP的方法可设状态f[i][j]为将前i首歌装入j张光盘所能存入歌曲的最大数目，显然f具有最优子结构，易得状态转移方程：
f[i][j]=max{f[k][j-1]+maxnum[k+1][i]}，其中maxnum代表第k+1至第i首歌装入一张盘所能存入的最大数目，可以用贪心计算
最终时间复杂度为O(N^2*M)，空间可以利用滚动数组优化到O(N)。

/*
ID: dementr1
PROG: rockers
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("rockers.in");
ofstream fout("rockers.out");
int a[21]={},sum[21][21]={},N,T,M,f[30][30]={};
void init()
{
	int i;
	fin>>N>>T>>M;
	for(i=1;i>a[i];
}
int num(int start, int end)
{
	bool used[21]={false};
	int now=0,ans=0,min,mini,i;
	if(end<start) return 0;
	while(1)
	{
		min=999999;
		for(i=start;i<=end;i++)
		{
			if(used[i]) continue;
			if(a[i]T) return ans;
		ans++;
	}
}
void dp()
{
	int i,j,k;
	for(i=1;i<=M+1;i++)
		for(j=0;j<=N;j++)
			for(k=0;k<=j;k++)
				f[i][j]=max(f[i][j],f[i-1][k]+num(k+1,j));
	fout<<f[M][N]<<endl;
}
int main()
{
	init();
	dp();
	return 0;
}