D - Cut Ribbon （dp）

Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Description

Polycarpus has a ribbon, its length isn. He wants to cut the ribbon in a way that fulfils the following two conditions:

Help Polycarpus and find the number of ribbon pieces after the required cutting.

Input

The first line contains four space-separated integersn, 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.

Output

Print a single number ― the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.

Sample Input

5 5 3 2

2

7 5 5 2

2

题目解析：

题目说给出给出一个绸缎的长度n。然后，是三个数，a,b,c。就是表示绸缎可以剪成a,b,c的长度。求，最多可以剪多少段？

思路解析：

刚看到题的时候，把or看成and了，靠。一开始用母函数写了一个。wrong了。之后才知道是一道dp。我们可以把n看成背包容积，把a,b,c看成不同的花费。则状态转移方程式为dp[i] = max(dp[i],dp[i-x]+1)(i-x>=0)表示当长度为i的时候考虑放x的性价比是多少。所以，我们可以用一个for就可以解决该问题了。

#include 
  
   
#include 
   
     const int INF = ~0U >>2; const int N = 4e3 + 5; int n,dp[N]; void Init() { for(int i = 0;i <= n;++i) dp[i] = -INF; } int main() { int a,b,c; while(~scanf("%d%d%d%d",&n,&a,&b,&c)) { Init();dp[0] = 0;// for(int i = 1;i <= n;++i) { if(i - a>=0){ if(dp[i] < dp[i-a]+1) dp[i] = dp[i-a]+1; } if(i - b >=0){ if(dp[i] < dp[i-b]+1) dp[i] = dp[i-b]+1; } if(i - c >=0){ if(dp[i] < dp[i-c]+1) dp[i] = dp[i-c]+1; } } printf("%d\n",dp[n]); } return 0; }