Codeforces #323 Div. 2 D Once Again...

2015/10/05 (Mon) Codeforces 貪欲 LIS ☆

問題

問題文

方針

$T \geq 300$ なら $a$ を $T$ 回繰り返す列を実際に作って LIS を求める． そうでないとき，まず $300$ 回繰り返した列の LIS を求め，その間に使わなかった $T-300$ 回に含まれる整数を挟む． 挟むのは $a$ に最も多く出現するものをその回数 $\times$ $300-T$ 個選ぶのが最適．

これで正しいらしいけど理由分かってない

行列累乗でも解けるらしい．

実装

int n,T;
vector<int> a;

vector<int> lis(const vector<int> &x) {
    int n = x.size();
    vector<int> dp(300*300+100, inf);
    for (int i = 0; i < n; i++){
        *upper_bound(dp.begin(), dp.begin() + n, x[i]) = x[i];
    }
    auto it = lower_bound(dp.begin(), dp.begin() + n, inf);
    return vector<int>(dp.begin(), it);
}

int solve(){
    int dec = max(0, T-300);
    T -= dec;
    vector<int> b;
    rep(i,T) rep(j,n) b.push_back(a[j]);
    vector<int> ls = lis(b);
    int freq = -1;
    map<int,int> count;
    rep(i,n) count[a[i]]++;
    for(auto & e : count){
        if(e.second > count[freq]){
            freq = e.first;
        }
    }
    return count[freq] * dec + ls.size();
}

signed main(){
    while(cin >> n){
        a.resize(n);
        cin >> T;
        rep(i,n) cin >> a[i];
        cout << solve() << endl;
    }
}