4269: 买iphone
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 1710 Solved: 316
Description
自从上次仓鼠中了1000万彩票后，彻底变成了土豪了，一群人愿意认他做干爹，仓鼠决定送他的干儿子每人一部iphone。仓鼠今天带了一群人去买iphone，每个人身上都背着一个大背包，只有3种背包，分别能装a，b，c个iphone，仓鼠希望每个人都能用iphone装满自己的背包。仓鼠有n个干儿子，也就是要买n部手机，仓鼠带了k个人去买手机，问是否存在一种情况能让每个买iphone的人的背包都装满
Input
输入包含多组测试数据，每组一行，包含5个整数n, k, a, b, c
(1 <= n, k , a, b, c <= 10000)
abc可以相同
Output
如果存在输出Yes，否则输出No
Sample Input
10 3 3 3 4
20 7 1 1 1
80 3 100 3 3
15 4 3 5 6
Sample Output
Yes
No
No
Yes
HINT
样例一3个人分别带大小为 3 3 4的背包去买手机正好每个人都装满
样例二 很明显只有一种背包，全部都是1也无法买20部iphone
样例四 4个人分别带大小为 3 3 3 6的背包去买手机正好每个人都装满
————————————————————————————
暴力枚举，如果分别枚举前两个包的数量肯定超时，由于我们只要判有没有可能，所以只需枚举价值最大的物品数目（也可以枚举其他的，这样可以减少次数），然后算下剩下的2种包有没有可能正好在数量为k-i时凑出n-a*i即可。
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define inf 0x3f3f3f3f int main()
{
int a[3],n,k;
while(~scanf("%d%d%d%d%d",&n,&k,&a[0],&a[1],&a[2]))
{
sort(a,a+3);
int flag=0;
for(int i=0; i<=k&&i*a[2]<=n; i++)
{
int m=n-a[2]*i;
int t=k-i;
if(t*a[0]>m||t*a[1]<m)
continue;
if(a[1]==a[0])
{
if(t*a[0]==m)
{
flag=1;
break;
}
else
continue; }
if((m-t*a[0])%(a[1]-a[0])==0)
{
flag=1;
break;
} }
if(flag==0)
printf("No\n");
else
printf("Yes\n"); } return 0;
}