# TopCoder SRM 588 DIV 2 maxSongs

By | September 3, 2013

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
{
}
};

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%>