charlieAndPilots.cpp

// Charlie and Pilots

// Charlie acquired airline transport company and to stay in business he needs to lower the expenses by any means possible. There are N pilots working for his company (N is even) 
// and N/2 plane crews needs to be made. A plane crew consists of two pilots - a captain and his assistant. A captain must be older than his assistant. Each pilot has a contract 
// granting him two possible salaries - one as a captain and the other as an assistant. A captain's salary is larger than assistant's for the same pilot. However, it is possible 
// that an assistant has larger salary than his captain. Write a program that will compute the minimal amount of money Charlie needs to give for the pilots' salaries if he decides 
// to spend some time to make the optimal (i.e. the cheapest) arrangement of pilots in crews.
// Input

// The first line of input contains integer N, 2 ≤ N ≤ 10,000, N is even, the number of pilots working for the Charlie's company.
// The next N lines of input contain pilots' salaries.
// The lines are sorted by pilot's age, the salaries of the youngest pilot are given the first. 
// Each of those N lines contains two integers separated by a space character, X i Y, 1 ≤ Y < X ≤ 100,000, a salary as a captain (X) and a salary as an assistant (Y).

// Output

// The first and only line of output should contain the minimal amount of money Charlie needs to give for the pilots' salaries. 

// Sample Input

// 4 
// 5000 3000 
// 6000 2000 
// 8000 1000 
// 9000 6000 

// Sample Output

// 19000 



#include<bits/stdc++.h>
using namespace std;

int getMinSalaryDp(pair<int, int> *salary, int captains, int assistants, int **dp) {

	if(captains == 0 && assistants == 0) {
		return 0;
	}

	if(dp[captains][assistants] != -1) {
		return dp[captains][assistants];
	}

	int ans = INT_MAX;
	if(assistants > 0) {
		ans = salary[0].second + getMinSalaryDp(salary+1, captains, assistants-1,dp);
	}
	if(assistants < captains) {
		ans = min(ans, salary[0].first + getMinSalaryDp(salary+1, captains-1, assistants,dp));
	}
	dp[captains][assistants] = ans;

	return ans;
}

int getMinSalary(pair<int, int> *salary, int n) {

	int **dp = new int*[n/2+1];
	for(int i = 0; i <= n/2; i++) {
		dp[i] = new int[n/2+1];
		for(int j = 0; j <= n/2; j++) {
			dp[i][j] = -1;
		}
	}

	int ans = salary[0].second + getMinSalaryDp(salary+1, n/2, n/2-1, dp);

	for(int i = 0; i <= n/2; i++) {
		delete [] dp[i];
	}
	delete [] dp;

	return ans;
}

int main() {

	int n;
	cin >> n;
	pair<int, int> *salary = new pair<int, int>[n];
	for(int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		salary[i] = make_pair(x, y);
	}

	int minSalary = getMinSalary(salary, n);

	cout << minSalary << endl;

	delete [] salary;
	return 0;
}