SRM348 div2 hard
メモ化再帰
"An increasing subsequence of a is maximal if unerasing any of the erased elements of a does not result in a longer increasing subsequence"
ていうのは消したものを追加しても追加前より長い"increasing subsequence"
になることはないよ、という意味らしい
英語の読解に15分くらいかかった
#include <algorithm> #include <vector> typedef long long LL; using namespace std; class IncreasingSubsequences { public: vector<int> a; LL cache[50+1]; int n; LL rec(int last) { LL &r=cache[last]; if(r!=-1) return r; r=0; int m=1000000000+10; for(int i=last+1;i<n;i++) { if(a[last]<a[i] && a[i]<m) { m=a[i]; r+=rec(i); } } if(r==0) r=1; return r; } LL count(vector<int> _a) { a=_a; reverse(a.begin(),a.end()); a.push_back(0); reverse(a.begin(),a.end()); fill(&cache[0],&cache[51],-1); n=a.size(); return rec(0); } };