小P的强力值

来源： http://hihocoder.com/problemset/problem/1358

关键思路：

每次选取使得(1+1/x)^a 最大的第x类属性, 提高该属性可使目标函数在当前的基准下增大的最快。感觉与梯度下降法有些相似之处，在目标函数为凸函数时这种方式求得的局部最优解也是全局最优的。

另外需要注意大数输出时的精度问题

具体实现：

#include #include #include using namespace std; #define SIZE 10 #define eps 1e-6 int N, K, a[SIZE], b[SIZE]; void init() { cin >> N >> K; for (int i = 0; i < K; ++i) cin >> a[i]; for (int i = 0; i < K; ++i) cin >> b[i]; } void solve() { double mx, tmp; int idx; for (int i = 0; i < N; ++i) { mx = 0; idx = -1; for (int j = 0; j < K; ++j) { tmp = pow(1 + 1.0 / a[j], 1.0 / b[j]); if (tmp - mx > eps) { mx = tmp; idx = j; } } ++a[idx]; } long double ans = 1.0; for (int i = 0; i < K; ++i) ans *= pow(a[i], 1.0 / b[i]); cout << fixed << setprecision(4) << ans << endl; } int main() { init(); solve(); return 0; }