Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-07-28

ThePriceIsRight

| 08:46

問題文

Longest increasing sub sequence を求める問題。再帰を使って解く方法は思いついたが、それでは計算量が問題になるとわかり、結局やはりEditorialを見た。dynamic programming による方法で解ける。

class ThePriceIsRight {
public:
    vector <int> howManyReveals(vector <int> prices) {
        const int size = prices.size();
        vector<int> S(size,0), L(size,0);
        vector <int> result(2,0);
        for (int i = 0; i < size; i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                if (prices[j] < prices[i]) 
                    tmp = max(tmp, S[j]);
            }
            for (int j = 0; j < i; j++) {
                if (S[j] == tmp && prices[j] < prices[i])
                    L[i] += L[j];
            }
            if (L[i] == 0) L[i] = 1;
            S[i] = 1 + tmp;
        }
        result[0] = *max_element(S.begin(), S.end());
        for (int i = 0; i < size; i++) {
            if (S[i] == result[0])
                result[1] += L[i];
        }
        return result;
    }
};