华电北风吹 天津大学认知计算与应用重点实验室 2016-08-14
题目链接: http://hihocoder.com/problemset/problem/1358
题目分析: 比赛的时候写的递归蛮算,超时,只得了30分。实际上是贪心。因为要求乘积最大,所以每次增加使得可以选择乘积增加倍数最大的是全局最优。
参考代码:
#include <iostream> #include <algorithm> #include <iomanip> using namespace std; int A[15]; double B[15]; int N, K; int main() { cin >> N >> K; for (int i = 0; i < K; i++) { cin >> A[i]; } for (int i = 0; i < K; i++) { double temp; cin >> temp; B[i] = 1.0 / temp; } while (N--) { int p = -1; double val = 0; for (int i = 0; i < K; i++) { double temp = pow((A[i] + 1.0) / A[i], B[i]); if (temp>val) { p = i; val = temp; } } A[p]++; } double result = 1.0; for (int i = 0; i < K; i++) { result *= pow(A[i], B[i]); } cout << fixed << setprecision(3) << result << endl; return 0; }