2 seconds
256 megabytes
standard input
standard output
Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:
- After the cutting each ribbon piece should have length a, b or c.
- After the cutting the number of ribbon pieces should be maximum.
Help Polycarpus and find the number of ribbon pieces after the required cutting.
The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) —
the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can
coincide.
Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.
5 5 3 2
2
7 5 5 2
2
In the first example Polycarpus can cut the ribbon in such way: the first piece has length 2, the second piece has length 3.
In the second example Polycarpus can cut the ribbon in such way: the first piece has length 5, the second piece has length 2.
解题说明：此题虽然是DP，但是可以用穷举的方法，外面两重循环用来判断a和b出现的次数，然后判断c是否满足条件即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include<set>
#include <algorithm>
using namespace std;
int main()
{
int n,a,b,c;
int i,j,t,max=0;
scanf("%d %d %d %d",&n,&a,&b,&c);
for(i=0;i*a<=n;i++)
{
for(j=0;i*a+j*b<=n;j++)
{
if((n-i*a-j*b)%c==0&&(n-i*a-j*b)/c+i+j>max)
{
max=(n-i*a-j*b)/c+i+j;
}
}
}
printf("%d\n",max);
return 0;
}