蓝桥杯2017年第八届真题-包子凑数 线性dp

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class 包子凑数 {
   static int dp[]=new int[100000];
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       int times = n;
       int result = 0;
       int temp = 0;
       while (times > 0) {
           int m = sc.nextInt();
           if (times == n)
               temp = m;
           temp = gcd(temp, m);
           for (int i = 1; i < dp.length; i++) {
               if (i % m == 0)
                   dp[i] = 1;
               if (i >= m && dp[i] == 0)
                   dp[i] = dp[i - m];
           }
           times--;
       }
       if (temp == 1) {
           for (int i = 1; i < dp.length; i++) {
               if (dp[i] == 0) {
                   result++;
               }
           }
           System.out.println(result);
       }
       else {
           System.out.println("INF");
       }
   }
       public static int gcd(int a,int b){
         return a%b==0?b:gcd(b,a%b);
       }
}