「何通りあるか」と「見ためが同じならば同じ解」っていう条件がいやらしい。
DP的な感じで解いた。
#include<cstdio> #include<algorithm> #include<map> #define rep(i,n) for(int i = 0; i < n; i++) #define fi first #define se second using namespace std; typedef pair<int,int> P; int main(){ int n, x, a, b, maxa = 0, ans = 0; map<int, P> dp; map<int, P>::iterator it; scanf("%d",&n); rep(i,n){ scanf("%d",&x); a = 0; b = 1; for (it = dp.begin(); it != dp.end(); it++) { if ((*it).fi > x) { if ((*it).se.fi > a){ a = (*it).se.fi; b = (*it).se.se; } else if ((*it).se.fi == a){ b += (*it).se.se; } } } maxa = max(maxa, a+1); dp[x] = P(a+1, b); } for (it = dp.begin(); it != dp.end(); it++) { if ((*it).se.fi == maxa) ans += (*it).se.se; } printf("%d %d\n", maxa, ans); return 0; }