Hatena::Grouptopcoder

cou929のTopCoder日記

2009-11-26

SRM453.5 div2 (再チャレンジ)

16:44

Hard - TheProduct

dynamic programming で解きます.kの値を1からひとつずつ増やしていくというアプローチをとります.二次元配列dpを作り,dp[i][j]にnumbers[j]よりも右側の要素から,i個取り出したときの最適解を保存するようにします.最終的にdp[k][i] (iは 0-numbers.size()) のうち最大値が解です.ただし今回の場合は,numbersの要素が負の値をとりうるので,負の値同士の乗算が奇数回起こった場合に,最適でない答えが出てしまいます.よって二次元配列を二つ作り,それぞれ最大値・最小値を保存するようにします.

class TheProduct {
public:
  long long maxProduct(vector <int> numbers, int K, int maxDist) {
    long long dpmax[11][51];
    long long dpmin[11][51];
    
    for (int i=0; i<11; i++)
      for (int j=0; j<51; j++)
        {
          dpmax[i][j] = LLONG_MIN;
          dpmin[i][j] = LLONG_MAX;
        }

    for (int i=0; i<numbers.size(); i++)
      dpmax[1][i] = dpmin[1][i] = numbers[i];

    for (int k=2; k<=K; k++)
      for (int i=0; i<numbers.size(); i++)
        for (int j=0; j<i; j++)
          if (i - j <= maxDist && dpmax[k-1][i] != LLONG_MIN)
            {
              dpmax[k][j] = max(dpmax[k][j], max(numbers[j] * dpmax[k-1][i], numbers[j] * dpmin[k-1][i]));
              dpmin[k][j] = min(dpmin[k][j], min(numbers[j] * dpmax[k-1][i], numbers[j] * dpmin[k-1][i]));
            }

    long long ret = LLONG_MIN;
    for (int i=0; i<numbers.size(); i++)
      ret = max(ret, dpmax[K][i]);

    return ret;
  }
};