我正在练习dp，我遇到了这个问题。http://www.spoj.com/problems/MPILOT/en/
查理收购了航空运输公司，为了保住生意，他需要尽一切可能降低费用。有N名飞行员为他的公司工作（N人是偶数），N/2的机组人员需要。一个机组由两名飞行员组成——一名机长和他的助手。上尉必须比助手大。每个飞行员都有一份合同，给他两份可能的薪水——一份是机长，另一份是助理。机长的薪水比同一飞行员的助手的高。然而，助手的薪水可能比船长高。编写一个程序，计算出如果查理决定花些时间对机组中的飞行员进行最佳（即最便宜的）安排，他需要为飞行员的工资支付的最低金额。
输入
第一行输入包含整数n，2≤n≤10000，n为偶数，为查理公司工作的飞行员人数。接下来的n行输入包含飞行员的工资。队伍按飞行员的年龄排序，最年轻的飞行员的工资是第一位的。这n行中的每一行都包含两个整数，由一个空格字符分隔，x i y，1≤y输出
第一条也是唯一一条输出线应该包含查理为飞行员工资所需的最低金额。
经过研究，我发现dp可以解决这个问题，但我到底该如何解决呢？我花了几个小时阅读这些链接，但没有找到一个容易理解的。请帮帮我。
最佳答案
像往常一样，我们需要找到一组紧的子问题。记住飞行员如何匹配的细节是不可能的——我们需要像下面这样的描述。
考虑一个标签，使每个飞行员都成为机长或助理，而不考虑匹配。当且仅当以下两个条件成立时，存在一个有效匹配：
有N/2队长和N/2助理。
对于每一个年龄段，至少有同样多的助手比这个年龄段年轻，而队长比这个年龄段年轻。
“唯一条件”的方向很简单：条件1是明显的，条件2是成立的，因为不等式适用于每个2飞行员机组，我们可以对不等式求和。
对于“如果”的方向，我们实际上必须建造船员。我们通过归纳法进行。如果没有飞行员，则空匹配有效。否则，由于最年轻的飞行员是助手（条件2），并且存在至少一个船长（通过条件1），所以存在（由斯佩纳引理，如果你想得到想象）一对飞行员，这样（a）没有飞行员年龄中等（B），年轻的一对是助手（C）年龄较大的一对是船长。配对并将其从池中移除。观察两个条件仍然成立，因此通过归纳假设来匹配其余条件。
这个观测结果产生了一个o（n^2）时间动态程序。我们反复阅读下一个年龄最大的飞行员的工资，然后计算出，鉴于到目前为止已经考虑了k名飞行员，从0到[k/2]的所有c，这些飞行员中支付k-c助理和c机长的最低费用。最后，返回支付N/2助理和N/2队长的费用。未经测试的蟒蛇：
def cost(pilots):
cost = [0]
for i, (assistant_salary, captain_salary) in enumerate(pilots):
cost.append(float('inf')) # two-way sentinel
cost = [min(cost[c] + assistant_salary,
cost[c - 1] + captain_salary)
for c in range((i + 1) / 2 + 1)]
return cost[-1] # i.e., N/2