SRM501 Div1 Easy - FoxPlayingGame
問題
0から始めて「xを足す」「yをかける」という操作を各a/b回好きな順番で行う
最後に得られる値の最大値を求める
解法
求める値は
(((x+x+..+x)*y +x+..+x)*y +x+...+x)*y +...
= x(y^k1 + y^k2 + ... + y^ka) (b>=k1>=k2>=...>=ka)
こういう形になる
yをかけると損をする場合(|y|<1)は一番最初に0にyをb回かけてしまえば消化できる
得をする場合(|y|>1)はxをa回足した後に一気にyをb回かけて指数を最大にするのが最善
あとyを1 or b-1回かけて符号を調整した方が良いケースも考えられる
結局a*xにyを0 / 1 / b-1 / b回かけた値のmaxが答えになる
場合分けがだるくて考えたんだけど厳密に証明しようとすると結局場合分けを考えないといけないし結構めんどい
何となくで提出するのも怖いしdpするのが無難だったと思う
class FoxPlayingGame { public: double theMax(int a, int b, int paa, int pab) { double x = 1.*paa/1000, y = 1.*pab/1000, res = a*x, t = a*x; rep(i,b) t *= y, chmax(res,t); return res; } };