Question

[编程题] 猜数游戏

Answer 1

时间限制：1秒
空间限制：32768K

这道题比较难。

首先运用动态规划的思想

首先我们分析，dp[i]表示前i个数的合法个数
当第i个数是素数的时候，前面除了1都没有能除尽的，所以这个位置可以随便选Y或N,所以dp[i] = dp[i-1]
当第i个数不是素数的幂次，比如6，10这种数，那么他们的情况实际上是被前面的数所决定的，对6来说，如果2，3为YY,那么6必然是Y，其他情况6必须是N,所以dp[i] = dp[i-1]
当第i个数是素数的幂次的时候，也就是2，4，8，16这种数，这时候情况就复杂了。假设现在有2，4，8，那么有多少种情况呢，我们仔细分析也能找出规律
YYY,YNN,NNN，YYN就这四种情况
对于2，4
YN,YY,NN三种情况
我们发现实际上也是有规律的，首先都能或者都不能两种，然后就是从左到右添加Y：
YNN,YYN。
所以对于这种情况，我们得出规律，如果有n个幂次，就有n+1中可行的情况。

分析完之后，我们就可以得出计算方法，对于12：
2，4，8这三个数是幂次，有4中可能
3，9 这两个数幂次，有三种可能
5，7，11，分别是两种可能
其他的数都由其他数决定
所以最后结果就是4 3 2 2 2

所以我们思考一下，最后就变成了找素数和素数幂次的个数了。

​