1569.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1569 on 2006-07-07 at 06:07:04 */ 
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 128, SN = 5;
const int SEQ_END = 9999, CASE_END = -9999;
const int F[] = { 1, 100, 100*100, 100*100*100, 100*100*100*100 };

vector<int> s[5];
int sn, ind[5];
set<int64> vst;

bool merge(int, int, int64);

int main()
{
	int t, T;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		bool end = false;
		int l = 0, h = 0;
		for(sn = 0; !end; sn++) {
			s[sn].clear();
			while(true) {
				int v; scanf("%d", &v);
				if(v == 0) continue;
				else if(v == SEQ_END) break;
				else if(v == CASE_END) { end = true; break; }
				else if(s[sn].size() > 0 && s[sn].back()*v > 0) s[sn].back() += v;
				else s[sn].push_back(v);
				l += v;
				if(v > 0) h += v;
			}
		}
		l = max(l, 0);
		while(h != l) {
			int mid = (h + l) / 2; 
			memset(ind, 0, sizeof(ind));
			vst.clear();
			if(merge(mid, 0, 0)) h = mid;
			else l = mid+1;
		}
		printf("%d\n", h);
	}
	
	return 0;
}

bool merge(int upl, int sum, int64 code)
{
	if(vst.count(code)) return false;
	vst.insert(code);
	int i, en = 0;
	for(i = 0; i < sn; i++)
		if(ind[i] == s[i].size()) en++;
		else if(s[i][ind[i]] <= 0) {
			sum += s[i][ind[i]]; ind[i]++;
			if(merge(upl, sum, code+F[i])) return true;
			else { ind[i]--; return false; }
		}
	if(en == sn) return true;
	for(i = 0; i < sn; i++)
		if(ind[i] != s[i].size() && sum+s[i][ind[i]] <= upl) {
			ind[i]++;
			if(merge(upl, sum+s[i][ind[i]-1], code+F[i])) return true;
			ind[i]--;
		}
	return false;
}