TopCoder上的FlowerGarden问题如何成为DP-one？

Question

我被杜米特鲁基于DP问题阅读本优秀教程这里。我正在尝试针对一维DP问题列表中提到的FlowerGarden问题提出一种基于DP的方法。

我只能想到一种非DP解决方案，该解决方案包括首先按顺序对花朵进行排序，然后根据问题中提到的不同条件检查对花朵进行重新排序。那不是归类为DP，是吗？

社论也没有提及有关DP的任何内容。任何人都可以通过任何机会为我指出基于DP的正确解决方案吗？

谢谢！

编辑：

我没有意识到该链接需要注册。这就是问题：

问题陈述您正在种满鳞茎的花园，一年四季都可以开花。但是，您希望种植花朵，以使它们在可见时不会阻塞其他花朵。

您将获得一个int []高度，一个int []花朵和一个int []枯萎。每种类型的花朵都由具有相同高度，花朵和枯萎指数的元素表示。高度代表每种类型的花朵生长的高度，绽放表示每种类型的花朵从地面弹出的早晨，枯萎表示每种类型的花朵枯萎并枯萎的夜晚。Bloom和wilt中的每个元素将是1到365之间的一个数字，并且wilt [i]始终大于bloom [i]。您必须将所有相同类型的花种在同一行中以外观，并且还希望将最高的花尽可能地向前。但是，如果某一种花比另一种花高，并且两种花都可以同时离开地面，较短的花必须种植在较高的花前面，以防止阻塞。一朵花在早晨开花，而在晚上凋谢，因此，即使一朵花在同一天开花，另一朵花在枯萎，一朵花也可以阻挡另一朵。

您应该返回一个int []，其中包含一些高度元素，顺序是您应该种花以达到上述目标。花园的前面由返回值中的第一个元素表示，是您从中查看花园的位置。高度元素将都是唯一的，因此将始终存在定义明确的顺序。

编辑二：

范例1：

高度= {5,4,3,2,1}

Bloom = {1,1,1,1,1}

wilt = {365,365,365,365,365}

返回：{1，2，3，4，5}

这些花都在1月1日盛开，在12月31日枯萎。由于它们可能彼此阻塞，因此必须将它们从最短到最高排序。

范例2：

h = {5,4,3,2,1}

b = {1,5,10,15,20}

w = {4,9,14,19,24}

返回：{5，4，3，2，1}现在，同一组花在不同的时间都盛开。由于它们永远不会互相阻挡，因此您可以将它们从最高到最短排序，以使最高的越远越好。

示例3：height = {5,4,3,2,1}

bloom = {1,5,10,15,20}

wilt = {5,10,14,20,25}

返回值：{3、4、5、1、2}这里的区别是第三种花比第四朵花早一天枯萎。因此，我们可以先放置高度为3的花朵，然后放置高度为4的花朵，然后放置高度为5的花朵，最后放置高度为1和2的花朵。请注意，我们也可以先对高度为1的花朵进行排序，但这不是导致最大可能的高度在花园中第一。

Answer 1

我也尝试解决这个问题。我的方法的主要思想是构建一棵树，其中每个子项都与其父项至少重叠一次。

例如，如果我们有三种高度为 4,2 和 1 的花在同一天生长和死亡，那么生成的树应该是：

另一方面，如果 4 和 2 以及 4 和 1 同时存在，但 2 和 1 不共存，则生成的树应该是：

这将生成一棵与问题约束一致的树。尽管如此，问题陈述还包括成本函数，使某些解决方案比其他解决方案更好。

...您还希望使更靠近前面的行中的花朵尽可能高。

将这种偏好投射到我们的树中的方法是将所有“兄弟”（共享同一父节点的所有节点）从较高到较低排序。所以2比1先出现。

我使用以下代码构建了这棵树：

#define INT_MOD(a,b) ((a<0)?(b+(a%b)):(a%b))
#define DIST(a,b) ((a-b>=0)?(a-b):(b-a))

//Prev: ForAll(i), bloom[i] < wilt[i]
inline bool isOverlap(vector<int> & bloom,
                      vector<int> & wilt,
                      vector<int> & height,
                      unsigned int idxPrev, unsigned int idxFollowing)
{
    int f1A = bloom[idxPrev];
    int f1B = wilt[idxPrev];
    int f2A = bloom[idxFollowing];
    int f2B = wilt[idxFollowing];

    bool notIntersecting = 
    f2A > f1B /* --[--]-(--)-- */ ||
    f1A > f2B /* --(--)-[--]-- */ ;

    return height[idxPrev] > height[idxFollowing] && !notIntersecting;
}


class CPreference {
public:
    static vector<int> * pHeight;
    static bool preference(int a, int b)
    {
        return (*pHeight)[a] > (*pHeight)[b];
    }
};
vector<int> * CPreference::pHeight = NULL;

vector<int> getOrdering(vector<int> height,
                        vector<int> bloom,
                        vector<int>  wilt)
{
    int l = height.size();
    vector<int> state = vector<int>(l, -1); /*  Tree where each leave points to its
                                                parent. Being that parent the first
                                                flower type that is forced to be
                                                after (backwards) its children */

    //This loop is the dynamic programming core.
    for(int i = 0; i < l; i++)
        for(int j = INT_MOD((i-1),l); j != i; j = INT_MOD((j-1),l))
        {
            if(isOverlap(bloom, wilt, height, i, j) &&
                (state[j] < 0 || DIST(height[j],height[i]) < DIST(height[j], height[state[j]])))
            {
                state[j] = i;
            }
        }

    vector<vector<int> > groups; //Groups of indexes overlapped by the element at the same index
    for(int i = 0; i < l+1; i++)
        groups.push_back(vector<int>()); // (l+1) for no overlapped indexes group.

    for(int i = 0; i < l; i++)
    {
        int k = state[i];
  if(k < 0) k = l;
  groups[k].push_back(i);
}

CPreference::pHeight = &height;
for(vector<vector<int> >::iterator it = groups.begin(); it != groups.end(); it++)
    sort(it->begin(),it->end(), CPreference::preference);

此时，组的每一行 (i)包含从高到低排序的所有花类型索引，这些索引应放置在索引i的花类型之前。

还需要最后一步，将组展平为输出向量。也就是说，构建一个向量，其中每个元素后跟以下任一元素：

• 它的父母在树上。
• 按身高排序时，它是下一个兄弟。

这可以通过深度访问group的每个节点来完成。我认为这是我的解决方案的弱点。我没有太多时间，所以我只是做了一个简单的递归实现：

//PRE: each vector, v, in 'groups' is sorted using CPreference
void flattenTree(vector<vector<int> > & groups, vector<int> & out, int currentIdx /*parent*/, int l)
{
    int pIdx = currentIdx;
    if(pIdx < 0) pIdx = l;

    vector<int> & elements = groups[pIdx];
    vector<int> ret;

    for(vector<int>::iterator it = elements.begin(); it != elements.end(); it++)
    {
        flattenTree(groups, out ,*it, l);
    }

    if(currentIdx>=0)
        out.push_back(currentIdx);
}

其中用于完成getOrdering函数：

vector<int> getOrdering(vector<int> height,
            vector<int> bloom,
            vector<int>  wilt)
{
  int l = height.size();
  vector<int> state = vector<int>(l, -1); /* Tree where each leave points to its
                         parent. Being that parent the first
                         flower type that is forced to be
                         after (backwards) its children */
  for(int i = 0; i < l; i++)
    for(int j = INT_MOD((i-1),l); j != i; j = INT_MOD((j-1),l))
      {
        if(isOverlap(bloom, wilt, height, i, j) &&
        (state[j] < 0 || DIST(height[j],height[i]) < DIST(height[j], height[state[j]])))
        {
            state[j] = i;
        }
      }

  vector<vector<int> > groups; //Groups of indexes overlapped by the element at the same index
  for(int i = 0; i < l+1; i++)
    groups.push_back(vector<int>()); // (l+1) for no overlapped indexes group.

  for(int i = 0; i < l; i++)
    {
      int k = state[i];
      if(k < 0) k = l;
      groups[k].push_back(i);
    }

  CPreference::pHeight = &height;
  for(vector<vector<int> >::iterator it = groups.begin();
      it != groups.end(); it++)
    sort(it->begin(),it->end(), CPreference::preference);

   vector<int> ret;
   flattenTree(groups, ret, -1, l);
   for(unsigned int i = 0; i < ret.size(); i++)
    ret[i] = height[ret[i]];
    return ret; 
}

如果您找到更好的解决方案或者知道任何改进我的解决方案的方法，请告诉我。