hdu 3496 Watch The Movie(DP)

클릭하여 링크 열기
제목:
**오늘 저녁에 영화를 봐야 하기 때문에 삼촌에게 영화를 사 달라고 했지만 영화를 볼 시간이 제한되어 있고 상점에서 파는 영화의 액수도 일정합니다.영화마다 가치가 있다.최대의 가치를 추구하다.만약 많이 산 영화를 다 보지 못하면 0을 출력한다.
T조 데이터가 있는데 n은 n종의 영화가 있음을 표시하고 m은 상점에서 가장 많이 파는 영화의 수를 표시하며 l은 이 저녁에 허용된 영화 관람 시간을 나타낸다.다음 n줄은 각 영화의 시간과 가치를 입력한다.
ｄｐ［ｊ］［ｋ］＝ｍａｘ(ｄｐ［ｊ－１］［ｋ－ｃｏｓｔ［ｉ］］＋ｖａｌｕｅ［ｉ］)
dp[j][k]는 시간을 들여 k가 j편의 영화를 보고 얻은 최대 가치를 나타낸다.
마지막으로 dp[m][l]의 존재 여부를 판단하면 됩니다!

#include"stdio.h"
#include"string.h"
#define max(x,y) x>y?x:y;
int dp[101][1001];
int main()
{
	int n,m,l,i,j,k;
	int t,cost[101],value[101];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&n,&m,&l);
		for(i=1;i<=n;i++)
			scanf("%d%d",&cost[i],&value[i]);
		memset(dp,-1,sizeof(dp));
		for(i=0;i<=l;i++)
			dp[0][i]=0;
		for(i=1;i<=n;i++)
		{
			for(j=m;j>=1;j--)
			{
				for(k=l;k>=cost[i];k--)
					if(dp[j-1][k-cost[i]]!=-1)
						dp[j][k]=max(dp[j][k],dp[j-1][k-cost[i]]+value[i]);
			}
		}
		if(dp[m][l]==-1)dp[m][l]=0;
		printf("%d
",dp[m][l]);
	}
	return 0;
}