Codeforces Round #323 (Div. 1) B. Once Again...

こどふぉの仕様変更でまた div2 になってしまいましたがまぁ div1 B はあんまり解けないので仕方ないですよね。ただ採点結果を見るのに時間がかかるのがちょっと辛いです。

問題

codeforces.com

解法

動的計画法で解きます。

dp[p][i][j] = (p 回数列が繰り返されているような数列の中で, から までの値のみを採用している時の LIS の最大の長さ)とします。
すると, dp[p][i][j] の値と dp[q][i][j] の値が分かっていれば,
dp[p+q][i][j] = max(dp[p][i][k] + dp[q][k][j]) (i <= k <= j) によって dp を求めていくことが出来ます。ですが, 今回は T の値が大きいので, dp[T][i][j] を正直に求めていくことが出来ません。

ですが, 上に書いた dp[p+q] の計算は, 実は行列の乗算と同じように計算することが出来ます。なので, 計算量は O() ではなく, O() で求められます。

今回の演算では単位行列となるのは対角線上に 1 が並んでいる行列ではなく, すべての値が 0 の行列であることに注意しましょう。

得た知見

• 行列の累乗で求められるとは全く考えてなかった
  • とりあえず最大値を取っていくような計算は行列のべき乗で表現できることは覚えておこう

typedef vector<int> vec;
typedef vector<vec> mat;

const int MAXN = 111;
const int INF = 1e9;
int a[MAXN];

mat mul(const mat& A, const mat& B) {
    int N = A.size();
    mat ret(N, vec(N, -INF));
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            ret[i][j] = max(ret[i][j], A[i][k] + B[k][j]);
        }
    }
    return ret;
}

mat pow_mat(const mat& A, int p) {
    int N = A.size();
    mat ret(N, vec(N)), cur = A;
    while (p) {
        if (p%2) ret = mul(ret, cur);
        cur = mul(cur, cur);
        p /= 2;
    }
    return ret;
}

int main() {
    int n, T;
    cin >> n >> T;
    for (int i = 0; i < n; i++) cin >> a[i];
    mat G(n, vec(n, -INF));
    for (int s = 0; s < n; s++) {
        for (int i = 0; i < n; i++) {
            if (a[i] < a[s]) continue;
            G[s][i] = 1;
            for (int j = 0; j < i; j++) if (a[j] <= a[i]) {
                G[s][i] = max(G[s][i], G[s][j] + 1);
            }
        }
    }
    G = pow_mat(G, T);
    int ans = 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ans = max(ans, G[i][j]);
    cout << ans << endl;
}