本文共 1548 字，大约阅读时间需要 5 分钟。
为了解决这个问题，我们需要设计一个高精度钟表的组合，使得在给定的预算内，指针方向组合的数量最大化。这个问题可以通过动态规划和数论中的质数幂次分解来解决。
#include#include #include #include using namespace std;vector generate_powers(int max_b) { vector ts; for(int p = 2; p <= max_b; ++p) { if (p == 1) continue; int current = p; while (current <= max_b) { ts.push_back(current); current *= p; } } sort(ts.begin(), ts.end()); ts.erase(unique(ts.begin(), ts.end()), ts.end()); reverse(ts.begin(), ts.end()); return ts;}int main() { const int MAX_B = 30000; vector ts = generate_powers(MAX_B); int T; scanf("%d", &T); for(int _ = 0; _ < T; ++_) { int b; scanf("%d", &b); if (b == 0) { printf("0.0000000000\n"); continue; } vector dp(b + 1, -1e18); dp[0] = 0.0; for(int ti : ts) { if (ti > b) continue; for(int i = b; i >= ti; --i) { if (dp[i - ti] != -1e18) { double new_val = dp[i - ti] + log(ti); if (new_val > dp[i]) { dp[i] = new_val; } } } } printf("%.9f\n", dp[b]); } return 0;}
generate_powers生成所有可能的质数幂次，直到它们不超过给定的最大预算值。这些值用于动态规划中的选择。dp，其中dp[i]表示在预算i下，最大乘积的对数值。初始时，dp[0]设为0，其他值设为一个很小的负数表示不可达。ti，我们从预算b开始倒序遍历，更新dp[i]的值。每次更新时，检查是否可以将ti加入当前预算，得到更大的乘积值。b对应的最大乘积的对数值。这种方法确保了在给定的预算内，找到最优的指针组合，使得组合数最大化。
转载地址：http://adio.baihongyu.com/