SRM501 Div1 Easy

250

DPして最大値を最小値を探す。
dp[足した回数][掛けた回数]



配るDPはできるんだけど、こういう貰うDPは結構苦手。

class FoxPlayingGame {
public:
  double theMax(int nA, int nB, int pA, int pB)
  {
    double sA = (double)pA / 1000.0;
    double sB = (double)pB / 1000.0;

    const int N = 50 + 1;
    double mx[N][N];
    double mn[N][N];

    mn[0][0] = mx[0][0] = 0;
    for (int i = 0; i <= nA; ++i) {
      mn[i][0] = mx[i][0] = i * sA;
    }
    for (int i = 0; i <= (int)nB; ++i) {
      mn[0][i] = mx[0][i] = 0;
    }
   
   
    for (int i = 1; i <= (int)nA; ++i) {
      for (int j = 1; j <= (int)nB; ++j) {
        {
          double a = mx[i - 1][j] + sA;
          double b = max(mx[i][j - 1] * sB, mn[i][j - 1] * sB);
          mx[i][j] = max(a, b);
        }
        {
          double a = mn[i - 1][j] + sA;
          double b = min(mx[i][j - 1] * sB, mn[i][j - 1] * sB);
          mn[i][j] = min(a, b);
        }
      }
    }

    return mx[nA][nB];
  }
};