2372.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 2372 on 2006-09-25 at 09:11:19 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100;
 
int main()
{
	int n, l[N];
	int e[N], cost[N];
	
	while(scanf("%d", &n) != EOF) {
		for(int i = 0; i < n; i++) scanf("%d", &e[i]);
		cost[0] = e[0]; l[0] = 1;
		for(int i = 1; i < n; i++) {
			cost[i] = e[i]; l[i] = 1;
			for(int j = i-1; j >= 0; j--) {
				if(e[i] > e[j]) continue;
				else if(cost[i] < cost[j]+e[i] 
					|| (cost[i] == cost[j]+e[i] && l[i] < l[j]+1)) 
					{ cost[i] = cost[j]+e[i]; l[i] = l[j]+1; }
			}
		}
		int mv = 0, ml = 0;
		for(int i = 0; i < n; i++)
			if(mv < cost[i] || (mv == cost[i] && ml < l[i])) { mv = cost[i]; ml = l[i]; }
		printf("%d %d\n", mv, ml);
	}
	
	return 0;
}