Post
by **dpitts** » Tue Mar 16, 2004 4:15 am

I got WA, even though it works with my test cases. Can someone give me some more test data, especially where it is wrong?

[cpp]

/* @JUDGE_ID: xxxxxx 10304 C++ */

#include <iostream>

#include <iomanip>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

using namespace std;

int buildTree(vector<int> &freqs, int start, int end, int depth)

{

if (start == end)

return 0;

int max = start;

for (int i = max+1; i < end; i++)

if (freqs* > freqs[max])*

max = i;

int cost = depth * freqs[max];

int minCost = buildTree(freqs, start, max, depth+1) +

buildTree(freqs, max+1, end, depth+1);

for (int j = max+1; j < end && freqs[j] == freqs[max]; j++)

{

int c = buildTree(freqs, start, j, depth+1) +

buildTree(freqs, j+1, end, depth+1);

if (c < minCost)

minCost = c;

}

return cost + minCost;

}

int main(int argc, char *argv[])

{

int n;

while (cin >> n)

{

vector<int> f;

int freq;

while (n--)

{

cin >> freq;

f.push_back(freq);

}

cout << buildTree(f, 0, f.size(), 0) << endl;

}

return 0;

}

[/cpp]