2001.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2001 on 2006-07-23 at 02:07:32 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 1600;

int sel[MAX][MAX], best[MAX], prev[MAX][MAX];

int main()
{
	priority_queue<int> Q;
	int t, T, i, j, k;
	int n, m, maxv, num[MAX];
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int total = 0;
		scanf("%d %d %d", &n, &m, &maxv);
		for(i = 0; i < n; i++) scanf("%d", &num[i]), total += num[i];
		if(total <= maxv || n <= m) { printf("%d\n", n); continue; }
		for(i = 0; i < n; i++) {
			while(!Q.empty()) Q.pop();
			int sum = 0;
			for(j = i; j < n; j++) {
				Q.push(num[j]); sum += num[j];
				if(sum > maxv) { sum -= Q.top(); Q.pop(); }
				sel[i][j] = Q.size();
			}
		}
		for(j = 0; j < n; j++)
			for(i = 0; i < n; i++)
				if(i == 0 || sel[i][j] != sel[i-1][j]) prev[i][j] = i-1;
				else prev[i][j] = prev[i-1][j];
		for(i = 0; i < m; i++)
			for(j = n-1; j >= i; j--)
				if(i == 0) best[j] = sel[0][j];
				else
					for(k = j; k > i; k = prev[k][j])
						best[j] = max(best[j], best[k-1]+sel[k][j]);
		printf("%d\n", best[n-1]);
	}
	
	return 0;
}