输入格式:第一行输入N(N<=100)表示流通的纸币面额数量;第二行N个纸币的具体表示的面额,从小到大排列,取值[1,10\^6]。
输出格式:输出一个整数,表示应该发行的纸币面额,这个整数是已经发行的所有纸币面额都无法表示的最小整数。(已经发行的每个纸币面额最多只能使用一次)
\#include "stdafx.h"\
int GeneratingFunction(){\
const int c\_size = 200;\
int b[c\_size];\
int coefficient[c\_size];\
int num;\
cin \>\> num;\
int denomination[c\_size];\
int total = 0;\
\
memset( b, 0, sizeof(b) );\
memset( coefficient, 0, sizeof(coefficient) );\
coefficient[0] = 1;\
for( int i = 1; i \<= num; i++ ){\
cin \>\> denomination[i];\
total += denomination[i];\
coefficient[denomination[i]] = 1;\
}\
\
// 若其可以表示所有整数,则total + 1必然无法表示.\
total += 1;\
//\
// 例如输入\
// 5\
// 1 2 3 9 100\
// 则将(1+x)\*(1+x\^2)\*(1+x\^3)\*(1+x\^9)\*(1+x\^100)前两个括号相乘,并将系数存储,\
// 然后将第三个括号与前面的结果相乘,以此类推.\
// 得到的最后的系数为0的则为无法用此面额表示的数字.\
//\
\
for( int i = 2; i \<= num; i++ ) // i:第i个括号,eg,(1+x)\*(1+x\^2)\*(1+x\^3)\*...\*(1+x\^n), i = 3,表示第三个括号,即(1+x\^3).\
{\
for( int j = 0; j \< 2\*denomination[i-1]; j++ ) // j:第i-1个括号中的第j个数.\
{\
for( int k = 0; k \<= denomination[i]; k += denomination[i] ) // 第i个括号中的各个数字的系数k.\
b[k+j] += coefficient[j];\
}\
\
for( int j = 0; j \< 2\*denomination[i]; j++ ){\
coefficient[j] = b[j];\
b[j] = 0;\
}\
}\
\
int i = 0;\
for( ; i \< total; i++ )\
if( coefficient[i] == 0 )\
break;\
return i;\
}\
int main(){\
cout \<\< GeneratingFunction() \<\< endl;\
}\
\
/\*\
5\
1 2 4 8 16\
32\
\
\
5\
1 2 3 9 100\
7\
\
\
5\
1 2 4 7 100\
15\
请按任意键继续. . .\
\*/