USACO 4.1 Beef McNuggets(DP)

前の試合で出会ったことがある.ずっと価値がaとbの2種類の貨幣だと思っていたが、最大のグループはa*b-a-bではない.のその後,aとbの2つが相互質であることが前提であることが分かった.
この結論を知って、このテーマはリュックサックに変わりました.どのように証明するか、私は考えていません.正確性も少し疑っています.しかし、コードデータはすべて過ぎました.

 1 /*

 2       ID: cuizhe

 3       LANG: C++

 4       TASK: nuggets

 5 */

 6 #include <cstdio>

 7 #include <cstring>

 8 #include <iostream>

 9 #include <cmath>

10 #include <algorithm>

11 using namespace std;

12 int p[11];

13 int dp[256*256];

14 int gcd(int a,int b)

15 {

16     return b == 0 ? a:gcd(b,a%b);

17 }

18 int main()

19 {

20     int n,i,j,v,key,flag;

21     freopen("nuggets.in","r",stdin);

22     freopen("nuggets.out","w",stdout);

23     scanf("%d",&n);

24     for(i = 1;i <= n;i ++)

25     scanf("%d",&p[i]);

26     if(n == 1)

27     {

28         printf("%d
",p[1]-1);

29         return 0;

30     }

31     sort(p+1,p+n+1);

32     key = p[1];

33     for(i = 2;i <= n;i ++)

34     key = gcd(key,p[i]);

35     if(key != 1)

36     {

37         printf("0
");

38         return 0;

39     }

40     flag = 1;

41     for(i = 1;i <= n&&flag;i ++)

42     {

43         for(j = i+1;j <= n&&flag;j ++)

44         {

45             if(gcd(p[i],p[j]) == 1)

46             {

47                 v = p[i]*p[j] - 1

48                 flag = 0;

49             }

50         }

51     }

52     dp[0] = 1;

53     for(i = 1;i <= n;i ++)

54     {

55         for(j = p[i];j <= v;j ++)

56         {

57             dp[j] += dp[j-p[i]];

58         }

59     }

60     for(i = v;i >= 1;i --)

61     {

62         if(dp[i] == 0) break;

63     }

64     printf("%d
",i);

65     return 0;

66 }