MPILOT - Pilots - Solution for SPOJ

Problem

https://vn.spoj.com/problems/MPILOT

https://oj.vnoi.info/problem/MPILOT

Charlie sở hữu vài cái máy bay bà già và cần tối ưu chi phi để kiếm lời

Có N phi công (N chẵn) và cần có N/2 phi hành đoàn.Mỗi phi hành đoàn gồm 2 người- 1 lái chính, 1 trợ lí. Lái chính phải cao tuổi hơn trợ lý. Hợp đồng cho mỗi phi công có ghi mức lương nếu anh ta là lái chính hoặc là trợ lí. Với mỗi 1 hợp đồng thì lương lái chính > lương trợ lí.

Tìm cách ghép cặp sao cho tổng lương phải trả cho N người là ít nhất.

Input

Dòng đầu là N (N chẵn), số phi công, 2 ≤ N ≤ 10,000.

N dòng tiếp theo, mỗi dòng là 2 số X,Y là lương phi công thứ i nếu làm lái chính hoặc trợ lí,1 ≤ Y < X ≤ 100,000.

Các phi công sắp tăng dần theo tuổi.

Output

Lương nhỏ nhất cần trả.

Sample

input 

3000 
2000 
1000 
6000 
 
output 


input 

7000 
3000 
4000 
1000 
3000 
6000 
 
output 


Tutorial

Gọi F[i][j] là tiền tối ưu khi xét hết i phi công, trong đó còn j trợ lí là chưa có ‘bồ’ (lái chính) ☺. Do đó, có hai trường hợp :

Thứ nhất : nếu i chọn làm lái chính thì F[i][j] = F[i-1][j+1] + giá_lái_chính(i). (cướp đi một con trợ lí ☺).

Thứ hai nếu i chọn làm trợ lí thì F[i][j] = F[i-1][j-1] + giá_trợ_lí(i). (làm giàu thêm đám trợ lí thêm một con ☹).

Nhận xét phi công thứ nhất luôn phải làm trợ lí, (ai biểu em ấy quá trẻ ☹) nên F[1][1] = giá_trợ_lí(1).

Nhận xét thứ hai là số lượng trợ lí mỗi gia đoạn ko lớn hơn i (số phi công hiện tại) và n/2 (tối đa n/2 trợ lí), do đó thuật có ĐPT O(N^2/2) = O(5*10^7).

Nhận xét kế tiếp là mảng F[i][] chỉ tính thông qua F[i-1][] nên có thể tạo mảng F[2][] để tiết kiệm bộ nhớ trong khi N <= 10000.

Submission

MPILOT.cpp

Tutorial SPOJ

MPILOT - Pilots