Maximizing the Profit | HourRank 27

素朴に考えると

dp[i][j] := i個の要素を使って、前の部品のprofit factorがjのときの最大profit

のようなDPを得る。 例えば、サンプルの入力で6, 8を使うと dp[2][8] = 6*8 のようになる。

この方法には問題が3つあるが、どれも対処できる。

(1) profit factorの幅が大きい

座標圧縮すればよい。

(2) 絶対値の大きな負の数をうまく扱えない

1, 1, -10, -10, 10

のような数列を考えれば {-10, -10, 10} のような構成になるが、これには1ではなく-10を使う必要がある。(-10<1)。 そこで、以下のようなDPを考える。

ma[i][j] := i個の要素を使って、前の部品のprofit factorがjのときの最大profit
mi[i][j] := i個の要素を使って、前の部品のprofit factorがjのときの最小profit

これで互いに値を見るように計算すればよい。

(3) DPの更新に時間がかかりすぎる

値p[k]を2番目の要素として計算することを考える。p[k]の圧縮後の座標をp'[k]とする。 ma[2][p'[k]] を更新するには ma[1][p'[k]-1], ma[1][p'[k]-2], ... , ma[1][0] と

mi[1][p'[k]-1], mi[1][p'[k]-2], ..., mi[1][0]　を見る必要がある。

ほしい値は前者の最大値と後者の最小値なので、値の更新が速いRMQでDPすればよい。

実行時間

O(Nlg(N))

const ll MA = (ll)2e18;
const ll MI = -(ll)2e18;
int N;
vi P;
// セグメント木を使ったRMQ
RMaxQ64 ma[4];
RMinQ64 mi[4];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    cin >> N;
    P.resize(N);
    rep(i, N)cin >> P[i];

    auto PP = compress(P);

    int M = sz(PP);
    rep(i, 4)ma[i] = RMaxQ64(M + 1, MI);
    rep(i, 4)mi[i] = RMinQ64(M + 1, MA);
    ma[0].update(0, 1);
    mi[0].update(0, 1);
    
    rep(i, N) {
        auto p = P[i];
        ll val = PP[p];
        for (int j = 2; j >= 0; --j) {
            ll x = ma[j].query(0, p + 1);
            ll y = mi[j].query(0, p + 1);
            if (x == MI)continue;
            x *= val;
            y *= val;
            if (x > y)swap(x, y);
            // x<=y
            if (x < mi[j + 1].query(p + 1, p + 2)) {
                mi[j + 1].update(p + 1, x);
            }
            if (y > ma[j + 1].query(p + 1, p + 2)) {
                ma[j + 1].update(p + 1, y);
            }
        }
    }

    ll ans = ma[3].query(0, M + 1);
    if (ans == MI)ans = -1;
    cout << ans << endl;
}