学步园

题目：有n集卡通，每一集的时间为t[i]，价值为v[i],选择m集，要在l时间内看完，问如何选择可以使家孩子最大。

分析：很裸的二维费用的背包，吧时间看成一维，集数看成一维，定义dp[i][j][k]为选择前i集，用j时间，看k集，所得的最大费用。

状态转移方程为：dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-t[i]][k-1]+v[i]);

初始化：dp[i][j][0]=0,看0集所得价值为0；

其他的其它的为非法。。。。

注意：看的集数k逆序 顺序都能过；那个注意看不到m集时，输出0，这种状态的表示，参考了别人的代码

#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
int t[110],v[110];
int dp[1100][110];
int main()
{
	int c;
	scanf("%d",&c);
	while(c--)
	{
		int  n,m,l;
		scanf("%d %d %d",&n,&m,&l);
		for(int i=1;i<=n;i++)
			scanf("%d %d",&t[i],&v[i]);
		memset(dp,-1,sizeof(dp));//不合法状态
		for(int i=0;i<1100;i++)
		     dp[i][0]=0;
		for(int i=1;i<=n;i++)
			for(int j=l;j>=t[i];j--)
				for(int k=m;k>=1;k--)//for(int k=1;k<=m;k++)
				   if(dp[j-t[i]][k-1]!=-1)//dp[][]==-1不合法，当然不能用
					   dp[j][k]=max(dp[j][k],dp[j-t[i]][k-1]+v[i]);
		if(dp[l][m]==-1)
			printf("0\n");
		else
			printf("%d\n",dp[l][m]);
	}
	//system("pause");
	return 0;
}