読者です 読者をやめる 読者になる 読者になる

PKU 1952 「BUY LOW, BUY LOWER」

PKU

「何通りあるか」と「見ためが同じならば同じ解」っていう条件がいやらしい。
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;
}