TopCoder SRM 588 DIV 2 maxSongs

TopCoder SRM 588 DIV 2 500 maxSongs

Failed to pass system tests during the competition through simple greedy strategy. I thought it can be solved by DP, but had no clear way to go.

After the competition, I finally found out that the result must be a subset of the vector sorted by tone!

So, we can degrade the original arrangement problem (O(n!)) to a combination problem (O(2^n)), and then calculate through simple brute force since the number of elements is less than 16. ~_~

It has a DP solution here, I would study it later.

My degraded brute force solution source in C++:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

struct song
{
	int dur;
	int tone;
	bool operator<(const song& a) const
	{
		return tone < a.tone;
	}
};

class GUMIAndSongsDiv2 {
public:
	int calc(vector<song> &s, int val, int T)
	{
		int ret = 0, sum = 0;
		int lastTone = -1;
		int i = 0;
		for (vector<song>::iterator it = s.begin(); it != s.end(); it ++)
		{
			if ((val & (1LL << i)) != 0)
			{
				sum += (*it).dur;
				if (lastTone >= 0)
				{
					sum += (*it).tone - lastTone;
				}
				lastTone = (*it).tone;
				ret ++;
			}
			i ++;
		}
		return sum <= T ? ret : 0;
	}
	int maxSongs(vector <int> duration, vector <int> tone, int T)
	{
		vector<song> s;
		for (int i = 0; i < duration.size(); i ++)
		{
			song so;
			so.dur = duration[i];
			so.tone = tone[i];
			s.push_back(so);
		}
		sort(s.begin(), s.end());
		int kinds = pow(2, duration.size());
		int maxCount = 0;
		for (int i = 0; i < kinds; i ++)
		{
			int cur = calc(s, i, T);
			if (cur > maxCount)
			{
				maxCount = cur;
			}
		}
		return maxCount;
	}
};

<%:testing-code%>
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!