UVA Homer Simpson(10465)

题目大意：

       Homer喜欢吃三明治，他吃Krusty三明治需要花m分钟，吃Kwik-e-Mart三明治需要花n分钟，现在给你t分钟，问Homer最多能吃几个三明治，若有剩余时间，则输出剩余时间，输出用空格隔开。

 

解题思路：

       完全背包问题，相当于问t分钟能够由几个m和几个n凑成，之前有硬币凑钱的题目，问的就是使用给定的硬币，有几种方法能够凑到M元，这题类似，只是要算出共需几个m和n才能凑成t分钟，若凑不成，输出剩余时间。只需稍微改一下状态方程：

                           dp[j] = dp[ j - times[i] ]+1 > dp[j] ? dp[ j - times[i] ]+1 : dp[j];

dp[ j - times[i] ]+1表示，若times[i]能够凑成 j ， 则dp[j] 就等于dp[ j - times[i] ]所需的硬币总数再加上 1 个硬币，且这个硬币就是times[i]。由于要求最大的，所以要和原来的dp[i]相比，取大者，比如15分钟，可以有3个5和5个3组成，则根据题目要求，应该取5个3。

 

代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

long long dp[10010] = {0};
long long times[2] = {0};

int main()
{

	long long m, n, t, beer;

	while( cin>>m>>n>>t )
	{
		memset( dp, 0, sizeof( dp ) );
		times[0] = m;
		times[1] = n;
		dp[0] = 1;
		for( int i = 0; i < 2; i++ )
		{
			for( int j = times[i]; j <= t; j++ )
			{
				if( dp[ j - times[i] ] )
				{
					dp[j] = dp[ j - times[i] ]+1 > dp[j] ? dp[ j - times[i] ]+1 : dp[j];
				}
			}
		}

		int tag = 0;
		for( int i = t; i >= 0; i-- )
		{
			if( dp[i] )
			{
				tag = i;
				beer = t - i;   //求剩余时间
				break;
			}
		}

		if( beer )
			cout<<dp[tag]-1<<" "<<beer<<endl;
		else
			cout<<dp[tag]-1<<endl;
	}

	return 0;
}