TopCoder SRM 159 DIV 1 Medium 練習

情報オリンピックに備えてC++での挑戦。

問題

与えられたシーケンスの中で単調増加の部分列のうち最も長いものの長さを求めよ。また、その長さの単調増加の部分列が何通りあるか求めよ。

解

T[i]はi番目の要素が最後にくる増加部分列のうち、最も長いものの長さとする。

また、V[i]をi番目の要素が最後にくる増加部分列で、その長さがT[i]のものが何通りあるかを表す。

あとはDP。

#define rep(i, c)   for(int i = 0; i < c; ++i)
#define reps(i,s,c) for(int i = s; i < c; ++i)
#define all(c)    (c).begin(), (c).end()
#define each(i, c)  for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)

using namespace std;

class ThePriceIsRight {
public:
  vector <int> howManyReveals(vector <int> prices) {
    vector<int> T(prices.size());
    vector<int> V(prices.size());
    T[0] = 1;
    V[0] = 1;
    for(int i=1; i<prices.size(); ++i){
      T[i] = 1;
      for(int j=0; j<i; ++j)
	if(prices[j]<prices[i])
	  T[i]=max(T[i],T[j]+1);
      V[i]=0;
      if(T[i] == 1)
	V[i]=1;
      else
	for(int j=0; j<i; ++j)
	  if(prices[j]<prices[i]&&T[j]+1==T[i])
	    V[i]+=V[j];
    }
    vector<int> res(2);
    int l = *max_element(all(T));
    res[0] = l;
    res[1] = 0;
    for(int i=0; i<T.size(); ++i)
      if(T[i]==l)
	res[1]+=V[i];
    return res;
  }
};