我正在练习动态规划,遇到了这个问题。 http://www.spoj.com/problems/MPILOT/en/
Charlie收购了一家航空运输公司,为了保持业务,他需要尽可能降低开支。 有N名飞行员在他的公司工作(N是偶数),并且需要组成N/2个机组。一个机组由两名飞行员组成-机长和他的助手。机长必须比他的助手年长。每位飞行员都有一份合同,授予他两种可能的薪水-一种是机长,另一种是助手。对于同一位飞行员而言,机长的薪水要高于助手的薪水。但是,助手的薪水可能比他的机长还高。编写一个程序,如果决定花费一些时间来制定飞行员组合的最佳(即最便宜)安排,则将计算Charlie需要支付的最小工资总额。
输入
输入的第一行包含整数N,2≤N≤10,000,N为偶数,表示Charlie公司工作的飞行员数量。接下来的N行输入包含飞行员的薪水。这些行按照飞行员的年龄排序,最年轻的飞行员的薪水排在第一位。每一行都包含两个由空格字符分隔的整数Xi和Yi,1≤Y< X ≤100,000,一个是船长的薪水(X),另一个是助手的薪水(Y)。
输出
输出的第一行应该包含Charlie需要支付给飞行员薪水的最少金额。
经过调查,我发现这可以通过DP来解决,但我该如何解决呢?我花了几个小时阅读链接,但没有一个容易理解的。请帮帮我。
输入
输入的第一行包含整数N,2≤N≤10,000,N为偶数,表示Charlie公司工作的飞行员数量。接下来的N行输入包含飞行员的薪水。这些行按照飞行员的年龄排序,最年轻的飞行员的薪水排在第一位。每一行都包含两个由空格字符分隔的整数Xi和Yi,1≤Y< X ≤100,000,一个是船长的薪水(X),另一个是助手的薪水(Y)。
输出
输出的第一行应该包含Charlie需要支付给飞行员薪水的最少金额。
经过调查,我发现这可以通过DP来解决,但我该如何解决呢?我花了几个小时阅读链接,但没有一个容易理解的。请帮帮我。