| Problem C: | Homer Simpson |
Time Limit: 3 seconds Memory Limit: 32 MB |
|
 |
Homer Simpson, a very smart guy, likes eating Krusty-burgers. It takes Homer m minutes to eat a Krusty- burger. However, there?s a new type of burger in Apu?s Kwik-e-Mart. Homer likes those too. It takes him n minutes to eat one of these burgers. Given t minutes, you have to find out the maximum number of burgers Homer can eat without wasting any time. If he must waste time, he can have beer. |
Input consists of several test cases. Each test case consists of three integers m, n, t (0 < m,n,t < 10000). Input is terminated by EOF.
For each test case, print in a single line the maximum number of burgers Homer can eat without having beer. If homer must have beer, then also print the time he gets for drinking, separated by a single space. It is preferable that Homer drinks as little beer as possible.
3 5 54 3 5 55
18 17
Problem setter: Sadrul Habib Chowdhury
Solution author: Monirul Hasan (Tomal)
Time goes, you say? Ah no!
Alas, Time stays, we go.
-- Austin Dobson
题意：
荷马.辛普森（Homer Simpson）是一个非常聪明的家伙。他很喜欢吃两种汉堡（我们称为A和B好了）。他吃一个A汉堡需要m 分钟，吃一个B汉堡需要n 分钟。如果有t 分钟时间的话，请你找出在不浪费一点点时间的情形下，辛普森先生最多可以吃多少个汉堡。如果必须要浪费时间（这个时候辛普森会喝啤酒），也请你找出尽可能少喝啤酒的情况下，他最多可以吃几个汉堡，还有花多少分钟喝啤酒。
以Sample Input的三组测试资料为例说明：
#include<iostream>
#include<cstring>
using namespace std;
int dp[5][10005],path[5][10005];
int arry[5];
int main()
{
int m,n,t;
while(cin>>m>>n>>t)
{
arry[0]=m,arry[1]=n;
memset(dp,0,sizeof(dp));
memset(path,0,sizeof(path));
for(int i=0;i<2;i++)
{
for(int j=0;j<=t;j++)
{
if(j<arry[i])
{
dp[i+1][j]=dp[i][j];
path[i+1][j]=path[i][j];
}
else
{
if(dp[i][j]>dp[i+1][j-arry[i]]+arry[i]||(dp[i][j]==dp[i+1][j-arry[i]]+arry[i]&&path[i][j]>path[i+1][j-arry[i]]))
{
dp[i+1][j]=dp[i][j];
path[i+1][j]=path[i][j];
}
else if(dp[i][j]<dp[i+1][j-arry[i]]+arry[i]||(dp[i][j]==dp[i+1][j-arry[i]]+arry[i]&&path[i][j]<=path[i+1][j-arry[i]]))
{
dp[i+1][j]=dp[i+1][j-arry[i]]+arry[i];
path[i+1][j]=path[i+1][j-arry[i]]+1;
}
//dp[i+1][j]=max(dp[i][j],dp[i+1][j-arry[i]]+arry[i]);
}
}
}
//cout<<dp[2][t]<<endl;
cout<<path[2][t];
if(t-dp[2][t]!=0) cout<<" "<<t-dp[2][t]<<endl;
else cout<<endl;
}
return 0;
}[动态规划]UVA10465 - Homer Simpson,布布扣,bubuko.com
[动态规划]UVA10465 - Homer Simpson
原文：http://blog.csdn.net/zju_ziqin/article/details/24270935