MPILOT spoj – Pilots

Nguồn đề bài: http://vn.spoj.com/problems/MPILOT/

1. Đề bài MPILOT spoj

Thử sub trước rồi hẵng đọc giải ha! <3

Charlie sở hữu vài cái máy bay bà già và cần tối ưu chi phi để kiếm lời

Có N phi công (N chẵn) và cần có N/2 phi hành đoàn.Mỗi phi hành đoàn gồm 2 người- 1 lái chính, 1 trợ lí. Lái chính phải cao tuổi hơn trợ lý. Hợp đồng cho mỗi phi công có ghi mức lương nếu anh ta là lái chính hoặc là trợ lí. Với mỗi 1 hợp đồng thì lương lái chính > lương trợ lí.

Tìm cách ghép cặp sao cho tổng lương phải trả cho N người là ít nhất.

Input

Dòng đầu là N (N chẵn), số phi công, 2 ≤ N ≤ 10,000.

N dòng tiếp theo, mỗi dòng là 2 số X,Y là lương phi công thứ i nếu làm lái chính hoặc trợ lí,1 ≤ Y < X ≤ 100,000.

Các phi công sắp tăng dần theo tuổi.

Output

Lương nhỏ nhất cần trả.

Sample

input
4
5000 3000
6000 2000
8000 1000
9000 6000

output
19000

input
6
10000 7000
9000 3000
6000 4000
5000 1000
9000 3000
8000 6000

output
32000

2. Gợi ý thuật toán MPILOT spoj

Quy hoạch động

Gọi f[i][j] là số tiền min khi xét tới phi công thứ i khi còn dư j trợ lí.

Do các phi công tăng dần theo tuổi nên có thể tính f[i][j] qua f[j-1][…]

Đọc code là ra CT luôn nè! Khó viết thế k biết 😀

3. Code mẫu MPILOT spoj

#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
typedef pair<int,int> II;
    int n,x[10001],y[10001],f[10001][10001];
int main()
{
    //freopen("mpilot.inp","r",stdin);
    //freopen("mpilot.out","w",stdout);
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d%d",&x[i],&y[i]);
    f[1][1]=y[1];
    for(int i=2; i<=n; i++)
    {
        f[i][0]=f[i-1][1]+x[i];
        f[i][i]=f[i-1][i-1]+y[i];
        for(int j=1; j<=i-1; j++)
            f[i][j]=min(f[i-1][j-1]+y[i],f[i-1][j+1]+x[i]);
    }
    printf("%d",f[n][0]);
}