usaco_3_4_4_rockers.cpp

usaco自己做的1到5章的代码

/*
PROB: rockers
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<memory>

using namespace std;
ifstream fin("rockers.in");
ofstream fout("rockers.out");
inline int maxof(int a,int b)
{
	return a>b?a:b;
}
int main()
{ 
	int dp[21][21][21];
	int ti[21];
	int i,j,k,t,m,n,s;
	memset(dp,0,sizeof(dp));
	fin>>n>>t>>m;
	i=1;j=1;
	while(i<=n)
	{
		fin>>s;
		if(s>t) i++;
		else {ti[j++]=s;i++;}
	}
	s=j-1;
	for(i=1;i<=s;i++)
		for(j=0;j<=m;j++)
			for(k=0;k<=t;k++)
			{
				if(k>=ti[i]) dp[i][j][k]=maxof(dp[i-1][j][k-ti[i]]+1,dp[i-1][j][k]);
				else if(j>0) dp[i][j][k]=maxof(dp[i-1][j-1][t-ti[i]]+1,dp[i-1][j][k]);
				else dp[i][j][k]=dp[i-1][j][k];
			}
	fout<<dp[s][m][0]<<endl;
	return 0;
}