动态规划，标准解

解题思路:

这一题有两个难点：

1为能否算出所有的能凑成的数（以10000为最大界限，因为Ai最大为100，N也才为100,10000足够代表所有的数了），

2为如何判断凑出来的数是否为无限个。

第一个难点：先找到s，接下来的问题就变成了：用a1...an，在1-s-1之间能凑成多少个数，用递归就能解决。

第二个难点在于思想，比如有三个数，2,6,9，如果能找到连续的两个数能用着三个数组成，那么这两个数后面的数都能被组成，只要不断在那两个数上加2就行。

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int dp[20005] = { 0 };

int a[105];

int main()

{

int n; cin >> n;

for (int i = 0; i < n; i++)

cin >> a[i];

dp[0] = 1;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < 10000; j++)//第一个难点

{

if (dp[j])

dp[j + a[i]] = 1;

}

}

int flag = 0, sum = 0,mi=10000;

for (int i = 0; i < n; i++)

mi = min(mi, a[i]);

for (int i = 0; i < 10000; i++)//第二个难点

{

if (dp[i])

sum++;

else

sum = 0;

if (sum == mi)//只要连续mi个能拼到，那么后面的也都可以

{

flag = 1;

break;

}

}

if (flag == 0)

cout << "INF" << endl;

else

{

int x = 0;

for (int i = 0; i < 10000; i++)

if (!dp[i])

x++;

cout << x << endl;

}

return 0;

}