c++ - 动态编程MPILOT

我正在尝试解决spoj(MPILOT)上的问题。

我知道这是一个动态编程问题，我也尝试过，但是给了我错误的答案。我的方法就像获取飞行员和助理的薪水差额并按降序排序，然后将0 - N/2添加为assistant，然后将N/2+1 - N添加为pilot并输出sum。但是问题出在飞行员必须比助手大的年龄条件上。

这是我的代码

#include <iostream>
#include <vector>
#include <algorithm>
#define lint long long

using namespace std;

struct pilot {
lint pilotsal;
lint assistantsal;
lint diff;
};

bool compare (pilot p1, pilot p2)
{
 return (p1.diff > p2.diff);
}

int main()
{
lint c,n,i;
lint sum=0,max=0;
 cin >> n;
vector <pilot> pilots(n);
for(i=0;i<n;i++)
{
    cin >> pilots[i].pilotsal >> pilots[i].assistantsal;
    pilots[i].diff= pilots[i].pilotsal-pilots[i].assistantsal;
}
 sum = max = pilots[0].assistantsal;
 sort(pilots.begin()+1,pilots.end(),compare);
for(i=1;i<=n/2-1;i++)
{
    sum+=pilots[i].assistantsal;
}

for(i=n/2;i<n;i++)
{
    sum+=pilots[i].pilotsal;
}
   cout << sum << endl;
   return 0;
}

请给我一些提示。如何检查问题的年龄条件。

最佳答案

一个小时的尝试使用“动态编程”解决此问题后，我得出结论，这不是适当的方法，但该问题尚未解决。我想到了许多贪婪的想法，但是在大多数情况下，贪婪并不好。

最后，我无法解决此问题，但是由于这个问题很有趣，所以我确实找到了解决方案，这是我对该解决方案的理解:

飞行员按升序排序:

第一位飞行员必须是助理

最后一位飞行员必须是机长

最糟糕的解决方案是当我们支付所有飞行员(机长和助手)作为机长时。这将是我们的第一个解决方案，我们将尝试将此金额减少到最低。

从将队长转为助理可以节省的是Pilot.CaptainWage - Pilot.AssistantWage。

问题变得很容易，因为仅需要最低工资，而不需要分组本身。

1. Set the first pilot as assistant
2. Insert each pilot in a list from the second to the last, and for every 2 new elements in the list
  // One pilot can be turned to an assistant only if remains at least another older pilot
  2.1 Select the pilot who contribute with the maximum saving so far
  2.2 Rest the saving of the previous step to our original solution
  2.3 Remove the pilot from the list
3. Print our new solution

注意:您需要一个有效的数据结构来快速获得具有最大节省量的飞行员，例如heap。

看看是否可以解决这个问题。我不会发布指向实际解决方案的链接，因为如果您先自己尝试，效果会更好:)。

关于c++ - 动态编程MPILOT，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16320310/