39. UVa-01047 Zones, <TLE>

아직 문제를 제대로 풀지 못했다.. 답은 맞을 것 같은데(uDebug에서 확인함) TLE때문에 안되니까 꼭 다시풀거다.

코드

 

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef vector<int> vi;
typedef vector<int>::iterator vit;
map<int,int> towers
int main() {
	int n, allowed,m,t,commonArea,temp,sum,idx,max,cases=0,people;
	int sign = 1;
	int	total = 0;
	int  j;

	vector<int> answer;
	/*
	n:number of towers planned
	allowed:number of towers allowed 
	*/
	while (cin >> n >> allowed) {
		if(cases)cout << endl;
		memset(towers, 0, sizeof(int) * 1024 * 1024);
		//input part
		if (n == 0 && allowed == 0) break;
		for (int i = 0; i < n; i++) cin >> towers[(1 << i)];

		cin >> m;
		for (int i = 0; i < m; i++) {
			cin >> t;

			if (t >= 3) {
				commonArea = 0;
				vi input_element;	//교집합의 idx를 모아놓은 vector
				input_element.reserve(30);
				for (int j = 0; j < t; j++) {
					cin >> temp;
					input_element.push_back((1 << (temp - 1)));
					commonArea |= (1 << (temp - 1));
				}
				cin >> people;
				towers[commonArea] = people;
			
				//교집합 후처리
				for (int num_of_el = 2; num_of_el <=t-1; num_of_el++) {
					vi onesAndZeros;
					onesAndZeros.reserve(30);
					for (int i = 0; i < t - num_of_el; i++) onesAndZeros.push_back(0);
					for (int i = 0; i < num_of_el; i++) onesAndZeros.push_back(1);
					int ind;
					do {
						ind = 0;
						for (int j = 0; j < t; j++) {
							ind |= (input_element[j] * onesAndZeros[j]);
						}
						towers[ind] += people;
					} while (next_permutation(onesAndZeros.begin(), onesAndZeros.end()));
				}
			}

			else {
				commonArea = 0;
				for (int j = 0; j < t; j++) {
					cin >> temp;
					commonArea |= (1 << (temp - 1));
				}
				cin >> people;	//number of people
				towers[commonArea] += people;
				//DEBUGING
			//	cout << "towers[" << commonArea << "]에 " << people << "를 넣었음" << endl;
			}
		}
		//outputpart
		sum = 0, max = 0;
		//Using next_permutation function, making subset
		int bits[30];
	
		for (int i = 0; i < allowed; i++) bits[i] = 1;
		for (int i = allowed; i < n; i++) bits[i] = 0;

		do {	//nCr가지 조합들 전부 포함됨
			//bits.
			vi indexes;
			indexes.reserve(30);
			int s = 0;
			for (int i = 0; i < n;i++) {
				if (bits[i] == 1) indexes.push_back((1 << (s)));
				++s;
			}
			int r = allowed;
			//함수파트 이식
			//r==allowed
			sign = 1;
			total = 0;
			for (int numOfOnes = 1; numOfOnes <= r; ++numOfOnes) {
				vi elementBit;
				elementBit.reserve(30);
				for (int i = 0; i < r - numOfOnes; i++) {
					elementBit.push_back(0);
				}
				for (int i = 0; i < numOfOnes; i++) {
					elementBit.push_back(1);
				}
				do {
					idx = 0; j = 0;
					for (vit it = elementBit.begin(); it != elementBit.end(); ++it) {
						idx |= indexes[j] * (*it);
						++j;
					}
					total += sign * towers[idx];
				} while (next_permutation(elementBit.begin(), elementBit.end()));
				sign *= -1;
			}
			sum = total;
			if (sum > max) {
				max = sum;
				answer = indexes;
			}
		} while (prev_permutation(bits, bits+n));

		//max를 출력
		cout << "Case Number  " << ++cases << endl;
		cout << "Number of Customers: " << max << endl;
		cout << "Locations recommended: ";
		for (int k = 0; k < allowed; ++k) cout << log2(answer[k]) + 1 << " ";

	}
	
	return 0;
}