题目大意:
输入一个N
再输入N个数(x1,x2....xn);
并给这N个数配一个系数 ci (ci 为非负正整数)
就变成了...
y=x1*c1+x2*c2+....xn*cn
不断变换各个系数可以求出很多不同的数字
但,并不是所有数字都能由整个式子得出的.
求
不能由整个式子得出的最大的数,
如果不存在
则输出0
思路:
首先是判断
这N个数字(x1,x2....xn)是否在某个数字之后便可以凑齐之后的所有数字
这个判断的依据在于在 这一组数字中是否存在至少一对数字互质.
如果没有,则直接输出0.
否则,则必能求得最大值
证明略..
判断之后
遍可以进行一个个数字的验证.
运用动态规划的想法.吧每一步的验证结果都保存到string中.
string初始化为="0";
令i从1开始,
如果不能由y组成1,则string+="0"
否则 string+="1";
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
.........
由此类推.
直到连续出现 '1' 的次数超过x1..
则可以输出 i-x1 了
因为之后的任何数都可以通过 i-x1 加上任意倍数的x1得到
比如
N个数为 3 6 10
i=17的时候 不能由 3,6,10组成
18可以由 6个3 组成
19可以由 10+6+3组成
20可以由 10+10 组成
21可以由 18+3 组成 (这里的18相等于上面的18 可以自行拆解)
22可以由 19+3 组成.. 以此类推