実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 446

問題概要

$N$ 棟のビルが等間隔に一列に並んでおり、手前から $i$ 番目のビルの高さは $H_i$ である。次の条件をともに満たすようにいくつかのビルを選んで電飾で飾るとき、最大でいくつのビルを選ぶことができるか求めよ。なお、ちょうど1つのビルを選んだときは条件を満たすとみなす。

選んだビルたちは高さが等しい。
選んだビルたちは等間隔に並んでいる。

制約

- 入力は全て整数。
$1 \leq N \leq 3000$
$1 \leq H_i \leq 3000$

考察

以下のような dp テーブル (dp<map<int, int>>) を用意して、動的計画法により解く。

$\mathrm{dp}_{i, d} :=$ 手前から $i$ 番目のビルを含み、間隔が $d$ で高さが $H_i$ のビルを選んでいくときの最大選択数

遷移は以下のようになる。

各 $i = 1, 2, \cdots, N$ に対して、ビル $j = 1, 2, \cdots, i$ が含まれるグループを見ていく。 $H_i \neq H_j$ の場合はビル $i$ は選べないのでスキップするとして、そうでないとき、
$\mathrm{dp}_{j}$ に $d = j - i$ が含まれるとき、 $\mathrm{dp}_{j, d}$ のグループにビル $i$ を追加することができるので、 $\mathrm{dp}_{i, d} = \mathrm{dp}_{j, d} + 1$ と遷移する。
そうでないとき、ビル $i, j$ の2つで新たにグループを作ることになるので、 $\mathrm{dp}_{j, d} = 2$ と遷移する。
上の2つの判定後、ans = max(ans, dp[j][d])で更新する。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> H(N);
    rep(i, 0, N) cin >> H[i];

    vector<map<int, int>> dp(N);
    int ans = 1;
    rep(i, 0, N)
    {
        rep(j, 0, i)
        {
            if (H[j] == H[i])
            {
                int d = i - j;
                if (dp[j].contains(d))
                {
                    dp[i][d] = dp[j][d] + 1;
                }
                else
                {
                    dp[i][d] = 2;
                }

                chmax(ans, dp[i][d]);
            }
        }
    }

    cout << ans << endl;
}