SRM499-550

SRM499-550.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#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;

class WhiteSpaceEditing {
public:
	int getMinimum(vector <int>);
	
	int rec(int start, int end, int level) {
		vector<int> splits;
		
		if (start==end)
			return 0;
		int minimum = lines[start];
		
		for (int i=start+1; i<end; ++i) {
			if ( lines[i] < minimum )
				minimum = lines[i];
		}
		
		for (int i=start; i<end; ++i) {
			if (lines[i]==minimum)
				splits.push_back(i);
		}
		
		int splits_num = splits.size();
		
		int cost = minimum - level + splits_num;
		
		for (int i=0; i<=splits_num; ++i) {
			int newstart = (i==0) ? start : splits[i-1]+1;
			int newend = (i==splits_num) ? end : splits[i];
			
			cost += rec(newstart, newend, minimum);
		}
		
		return cost;
	}
	
	vector<int> lines;
};

int WhiteSpaceEditing::getMinimum(vector <int> _lines) {
	lines = _lines;
	
	return rec(0, lines.size(), 0) - 1;
}