POJ 1952 BUY LOW, BUY LOWER

問題文

典型DP。やるだけ。頭悪い。

#include <set>
#include <algorithm>
#include <queue>
#include <utility>
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
typedef pair<int,int> P;
P dp[5003];
int a[5003];
int main(){
	int n;
	for(int i = 0;i <= 5000;i++){
		dp[i].first = 1;
	}
	scanf("%d",&n);
	int q = 0;
	while(cin >> a[q])q++;

	for(int i = 1;i <= n;i++){
		set<int> s;
		set<int>::iterator it;
		for(int j = 1;j < i;j++){
			if(a[i-1] < a[j-1]){
				dp[i].first = max(dp[i].first,dp[j].first+1);
			}
		}
		for(int j = i-1;j >= 1;j--){
			if(a[i-1] < a[j-1] && dp[j].first == dp[i].first-1){
				it = s.find(a[j-1]);
				if(it == s.end()) dp[i].second += dp[j].second;
				s.insert(a[j-1]);
			}
		}
		if(dp[i].first == 1){
			dp[i].second = 1;
		}
	}

	int ans = 0;
	int ans2 = 0;
	for(int i = 1;i <= n;i++){
		ans = max(ans,dp[i].first);
	}

	set<int> s;
	set<int>::iterator it;

	for(int i = n;i >= 1;i--){
		if(dp[i].first == ans){
			it = s.find(a[i-1]);
			if(it == s.end())ans2 += dp[i].second;
			s.insert(a[i-1]);
		}
	}

	printf("%d %d\n",ans,ans2);

	return 0;
}