题意：给出n个数，问你从中选出至少多少个数才能使它们的为1，如果无解输出-1。
题解：看上去一副不可做的样子。。
我们设f[i][j]表示选了i个数，是否能使它们的为1。
转移有点麻烦，不能用0/1来表示，应该用方案数来表示（因为有倍数的问题）。
但这样的时间复杂度看上去是n^2*sqrt(n)的。但仔细观察，你会发现，如果一定有解，那么你每次多选一个数的时候，必然会将它们的至少除以2，然后300000的范围的话你就只要最多做6/7次（不太清楚），也就是选这么几个数，就能使变为1辣。
时间复杂度O(7*n*sqrt(n))
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- pqdy.cn 版权所有 赣ICP备2024042791号-6
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务