algorithm dynamic_programming

看起来像什么样子 FlowerGarden pr0blem 在 TopCoder a DP-one?

我在基于的问题上阅读了这本优秀的Dumutra教科书 DP
http://www.topcoder.com/tc%3Fd ... tatic
. 而且我正试图提出一种基于的方法 DP, 对于一个问题
http://community.topcoder.com/ ... D5006
, 在问题列表中提到 1D DP.

我只能考虑与之相关的决定 DP, 这将包括按顺序排序颜色的初始排序，然后根据任务中提到的条件的各种检查重新排序。它没有被归类为 DP, 是不是？

编辑文章也没有说 DP.
任何人都可以不小心向我施加对此问题的正确解决方案 DP?

谢！

编辑：

我不知道链接需要注册。这是问题所在的地方：

分期任务
你用灯泡种植花园，全年给你快乐的花朵。但是，你想植花
这样他们就不会阻挡其他花朵。

你会得到 int[] 生长， int[] 开花I. int[] 枯萎。
每种类型的花由具有相同索引的元素表示。
高度，开花和褪色。高度代表高度
每种花类型，盛开代表每种花型时的早晨
它流出了地面，苗条代表每种类型的花都从地面流出时。
花皱纹和模具的类型。开花和褪色中的每个元素
将有一个数字 1 到 365 包容性，我 wilt[i] 总是
会有更多 bloom[i]. 你必须种植这个世界的所有颜色。
出现一行中的相同类型，您也想要拥有
最高的花朵如下。但是，如果一个
花的类型高于另一个，两种类型都可以是
陆地同时，必须以较短的花卉种植
较高的花以防止阻塞。花朵绽放
早上和晚上褪色，所以即使一朵花绽放
在同一天，逐渐消失，一个人可以阻挡另一个花。

你必须返回 int[], 其中包含高度的元素
您必须种植颜色以实现上述目标的顺序。
花园的前部由您的返回中的第一个元素表示
从你看着花园的意思是那里。高度元素
一切都是独一无二的，所以总会有明确的顺序。

编辑二：

例子 1:

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

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

Wilt = {365,365,365,365}

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

所有这些花朵绽放 1 1月份和褪色 31 十二月。由于它们都可以互相阻塞，因此必须将它们从最短到最短的流中流。

例子 2:

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

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

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

返回： { 5, 4, 3, 2, 1 }
同一组颜色现在在不同的时间开花。由于它们永远不会互相阻挡，因此您可以从最高到最短的最短以获得最高的前方。

例子 3:
高度= {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, 但这不会导致最高可能的高度将成为花园中的第一个。

已邀请:

11 个回复

郭文康

赞同来自:

这不是动态编程问题。这是贪婪算法的问题。

它也让我尴尬，因为
https://www.topcoder.com/commu ... nced/
将其指在该部分中的实际任务 “Elementary”.

从最短到最短的最短鲜花。从空白的行列表开始。对于每朵花 /从最短到最高点/ 找到你可以插入这朵花的最前部的地方，以便它不会阻挡他身后的花朵。

在 Python 年：

def getOrdering/height, bloom, wilt/:

 flowers = zip/height, bloom, wilt/

 flowers.sort//



 def flowersOverlap/f1, f2/:

 # Overlap if each blooms before the other wilts.

 return f2[1] <= f1[2] and f1[1] <= f2[2]



 rows = [ ]

 for flower in flowers:

 rowIndex = len/rows/

 # Start at the back and march forward as long as

 # `flower` wouldn't block any flowers behind it.

 while rowIndex > 0 and not flowersOverlap/flower, rows[rowIndex - 1]/:

 rowIndex -= 1

 rows[rowIndex:rowIndex] = [flower]



 return [flower[0] for flower in rows]

莫问

赞同来自:

public int[] getOrdering/int[] height, int[] bloom, int[] wilt/ {

 int[] optimal = new int[height.length];

 int[] optimalBloom = new int[bloom.length];

 int[] optimalWilt = new int[wilt.length];



 // init state

 optimal[0] = height[0];

 optimalBloom[0] = bloom[0];

 optimalWilt[0] = wilt[0];



 // run dynamic programming

 for/int i = 1; i < height.length; i ++/ {

 int currHeight = height[i];

 int currBloom = bloom[i];

 int currWilt = wilt[i];



 int offset = 0; // by default, type i is to be put to 1st row

 for/int j = 0; j < i; j ++/ {

 if/currWilt >= optimalBloom[j] && currWilt <= optimalWilt[j] ||

 currBloom >= optimalBloom[j] && currBloom <= optimalWilt[j] ||

 currWilt >= optimalWilt[j] && currBloom <= optimalBloom[j]/ { // life period overlap

 if/currHeight < optimal[j]/ { // life overlap, and type i is shorter than type j

 offset = j;

 break;

 } else {

 offset = j + 1; // type i overlap with type j, and i is taller than j. Put i after j

 }

 } else { // not overlap with current

 if/currHeight < optimal[j]/ {

 offset = j + 1; // type i not overlap with j, i is shorter than j, put i after j

 }

 // else keep offset as is considering offset is smaller than j

 }

 }



 // shift the types after offset

 for/int k = i - 1; k >= offset; k -- / {

 optimal[k+1] = optimal[k];

 optimalBloom[k+1] = optimalBloom[k];

 optimalWilt[k+1] = optimalWilt[k];

 }

 // update optimal

 optimal[offset] = currHeight;

 optimalBloom[offset] = currBloom;

 optimalWilt[offset] = currWilt;

 }

 return optimal;

}

这是我经过验证的工作代码。

裸奔

赞同来自:

我一整天都在挣扎着这个准确的问题，而且，我找不到他的任何解决方案。

这是我的贪婪方法 java, 类似于其他，已经发布，关键点是按高度的顺序行动。原因是避免使用中高 /召回已经计算过/, 考虑到这一点

中间高度可以改变先前计算的相对顺序

.

int[] height = new int[]{5, 3, 4};

int[] start = new int[]{1, 3, 1};

int[] end = new int[]{2, 4, 4};

System.out.println/Arrays.toString/new FlowerGarden//.getOrdering/height, start, end///;

这是我能找到的唯一最佳子结构。但考虑到字幕之间没有重叠，不应考虑该算法 DP, 和贪婪。

private static boolean intersects/final int[] starts, final int[] ends, int i1, int i2/ {

 return !/ends[i1] < starts[i2] || ends[i2] < starts[i1]/;

}



public int[] getOrdering/final int[] height, final int[] starts, final int[] ends/ {



 PriorityQueue<integer> minHeap = new PriorityQueue<integer>/new Comparator<integer>// {

 public int compare/Integer i, Integer j/ {

 return Integer.compare/height[i], height[j]/;

 }

 }

 /;

 for /int i = 0; i &lt; height.length; i++/ {

 minHeap.add/i/;

 }

 LinkedList<integer> list = new LinkedList<integer>//;

 while /minHeap.size// &gt; 0/ {

 Integer index = minHeap.poll//;

 int p = 1;

 int pos = 0;

 for /Integer i : list/ {

 if /intersects/starts, ends, i, index// {

 pos = p;

 }

 p++;

 }

 list.add/pos, index/;

 }

 int[] ret = new int[height.length];

 int j = 0;

 for /Integer i : list/ {

 ret[j++] = height[i];

 }

 return ret;

}

BTW, 解决方案 DP, 在这个例子中，我在这里看到了这一点。

舟
</integer></integer></integer></integer></integer>

莫问

赞同来自:

package topcoders;



import java.util.ArrayList;

import java.util.List;



public class FlowerGarden {



 public int[] getOrdering/int[] height, int[] bloom, int[] wilt/ {

 int[] order = new int[height.length];

 List<integer> heightList = new ArrayList<integer>//;

 for /int i = 0; i &lt; height.length; i++/ {

 heightList.add/height[i]/;

 }

 heightList = quickSort/heightList/;

 for /int i = 0; i &lt; height.length; i++/ {

 height[i] = heightList.get/i/;

 }

 order = height;

 for /int i = 0; i &lt; order.length; i++/ {

 int j = 0;

 while /j &lt; order.length - 1

 &amp;&amp; isBlocking/j + 1, j, order, bloom, wilt// {

 int placeHolder = order[j];

 order[j] = order[j + 1];

 order[j + 1] = placeHolder;

 j++;

 }

 }



 return order;

 }



 public boolean isBlocking/int isBlocked, int isBlocking, int[] order,

 int[] bloom, int[] wilt/ {

 if /order[isBlocking] &gt; order[isBlocked]

 &amp;&amp; bloom[isBlocked] &lt;= wilt[isBlocking]

 &amp;&amp; wilt[isBlocked] &gt;= bloom[isBlocking]/ {

 return true;

 } else {

 return false;

 }

 }



 public List<integer> quickSort/List<integer> array/ {

 if /array.size// &lt;= 1/ {

 return array;

 }

 int pivotIndex = array.size// / 2;

 int pivot = array.get/pivotIndex/;

 List<integer> less = new ArrayList<integer>//;

 List<integer> greater = new ArrayList<integer>//;

 int l = 0;

 int g = 0;

 for /int i = 0; i &lt; array.size//; i++/ {

 if /i == pivotIndex/ {

 continue;

 } else if /array.get/i/ &gt;= pivot/ {

 less.add/array.get/i//;

 } else {

 greater.add/array.get/i//;

 }

 }

 List<integer> lessResult = quickSort/less/;





 List<integer> greaterResult = quickSort/greater/;



 List<integer> result = new ArrayList<integer>//;

 result.addAll/lessResult/;

 result.add/pivot/;

 result.addAll/greaterResult/;







 return result;

 }



 public static void main/String[] args/ {

 int[] height = { 5, 4, 3, 2, 1 };

 int[] bloom = { 1, 5, 10, 15, 20 };

 int[] wilt = { 5, 10, 14, 20, 25 };

 FlowerGarden g = new FlowerGarden//;

 List<integer> arrayList = new ArrayList<integer>//;

 int[] array = g.getOrdering/height, bloom, wilt/;

 for /int i = 0; i &lt; array.length; i++/ {

 System.out.println/array[i]/;

 }

 }

}

</integer></integer></integer></integer></integer></integer></integer></integer></integer></integer></integer></integer></integer></integer>

裸奔

赞同来自:

我也试图解决这个问题。我的方法的主要思想是建立一棵树，其中每个孩子至少会重叠它的父母。

例如，如果我们有三种类型的颜色高度 4,2 和 1, 在同一天生长和死亡，得到的树应该是：

另一方面，如果 4 和 2 和 4 和 1 同时生活但是 2 和 1 不要共存，那么得到的树应该是：

这将创建一个与问题禁忌症一致的树。尽管如此，问题的设置还包括成本函数，使其比其他解决方案更好。

..你还想要在靠近前方的行中的鲜花，尽可能高。

在树上投射这种偏好的方法是安排所有 "brothers" /所有具有相同父级的节点/ 从较高到更低。因此， 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> &amp; bloom,

 vector<int> &amp; wilt,

 vector<int> &amp; 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 &gt; f1B /* --[--]-/--/-- */ ||

 f1A &gt; f2B /* --/--/-[--]-- */ ;



 return height[idxPrev] &gt; height[idxFollowing] &amp;&amp; !notIntersecting;

}





class CPreference {

public:

 static vector<int> * pHeight;

 static bool preference/int a, int b/

 {

 return /*pHeight/[a] &gt; /*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 &lt; 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/ &amp;&amp;

 /state[j] &lt; 0 || DIST/height[j],height[i]/ &lt; DIST/height[j], height[state[j]]///

 {

 state[j] = i;

 }

 }



 vector<vector<int> &gt; groups; //Groups of indexes overlapped by the element at the same index

 for/int i = 0; i &lt; l+1; i++/

 groups.push_back/vector<int>///; // /l+1/ for no overlapped indexes group.



 for/int i = 0; i &lt; l; i++/

 {

 int k = state[i];

 if/k &lt; 0/ k = l;

 groups[k].push_back/i/;

}



CPreference::pHeight = &amp;height

for/vector<vector<int> &gt;::iterator it = groups.begin//; it != groups.end//; it++/

 sort/it-&gt;begin//,it-&gt;end//, CPreference::preference/;

此时每一行 /i/

团体

包含，从较高到更高的索引，所有类型颜色的索引必须放在索引花的类型前

i

.

最后一步是必要的

团体

在输出矢量。也就是说，构建每个元素应该是：

他的父母在树上。

他是下一个弟弟，当时身高。

这可以通过对每个节点的深度访问来完成。

团体

. 我认为这是我决定的弱点。我没有那么多时间，所以我刚刚制作了天真的递归实施：

//PRE: each vector, v, in 'groups' is sorted using CPreference

void flattenTree/vector<vector<int> &gt; &amp; groups, vector<int> &amp; out, int currentIdx /*parent*/, int l/

{

 int pIdx = currentIdx;

 if/pIdx &lt; 0/ pIdx = l;



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

 vector<int> ret;



 for/vector<int>::iterator it = elements.begin//; it != elements.end//; it++/

 {

 flattenTree/groups, out ,*it, l/;

 }



 if/currentIdx&gt;=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 &lt; 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/ &amp;&amp;

 /state[j] &lt; 0 || DIST/height[j],height[i]/ &lt; DIST/height[j], height[state[j]]///

 {

 state[j] = i;

 }

 }



 vector<vector<int> &gt; groups; //Groups of indexes overlapped by the element at the same index

 for/int i = 0; i &lt; l+1; i++/

 groups.push_back/vector<int>///; // /l+1/ for no overlapped indexes group.



 for/int i = 0; i &lt; l; i++/

 {

 int k = state[i];

 if/k &lt; 0/ k = l;

 groups[k].push_back/i/;

 }



 CPreference::pHeight = &amp;height

 for/vector<vector<int> &gt;::iterator it = groups.begin//;

 it != groups.end//; it++/

 sort/it-&gt;begin//,it-&gt;end//, CPreference::preference/;



 vector<int> ret;

 flattenTree/groups, ret, -1, l/;

 for/unsigned int i = 0; i &lt; ret.size//; i++/

 ret[i] = height[ret[i]];

 return ret; 

}

如果您找到了最佳解决方案或了解改善我的方法，请告诉我。
</int></vector<int></int></vector<int></int></int></int></int></int></int></int></int></int></int></vector<int></vector<int></int></vector<int></int></int></int></int></int></int></int></int></int></int></int>

卫东

赞同来自:

排序的拓扑方法：

#include<stdio.h>

#include<stdlib.h>

#include <vector> 

#include <queue> 



using namespace std;



#define MAX_FLOWERS 50



struct flower

{

 int id;

 int height;

 int bloom;

 int wilt;

 bool visited;

 int ind;

};



struct flower_comp

{

 bool operator///const struct flower* lhs, const struct flower* rhs/ const

 {

 return rhs-&gt;height &gt; lhs-&gt;height;

 } 

};



inline bool overlap/const struct flower&amp; a, const struct flower&amp; b/

{

 return !//a.bloom &lt; b.bloom &amp;&amp; a.wilt &lt; b.bloom/ || /a.bloom &gt; b.bloom &amp;&amp; a.bloom &gt; b.wilt//;

}



void getOrdering/int height[], int bloom[], int wilt[], int size/

{

 struct flower flowers[MAX_FLOWERS];



 for/int i = 0; i &lt; size; i++/

 {

 flowers[i].id = i;

 flowers[i].height = height[i];

 flowers[i].bloom = bloom[i];

 flowers[i].wilt = wilt[i];

 flowers[i].visited = false;

 flowers[i].ind = 0;

 } 



 bool partial_order[MAX_FLOWERS][MAX_FLOWERS] = {false};



 for/int i = 0; i &lt; size; i++/

 {

 for/int j = i + 1; j &lt; size; j++/

 {

 if/overlap/flowers[i], flowers[j]//

 { 

 if/flowers[i].height &lt; flowers[j].height/

 {

 partial_order[i][j] = true;

 flowers[j].ind++; 

 }

 else

 {

 partial_order[j][i] = true;

 flowers[i].ind++; 

 }

 }

 }

 }



 priority_queue<struct flower*="" flower*,="" vector<struct="">, flower_comp&gt; pq;



 for/int i = 0; i &lt; size; i++/

 {

 if/flowers[i].ind == 0/

 {

 pq.push/&amp;flowers[i]/;

 }

 }



 printf/"{"/;

 bool first = true;

 while/!pq.empty///

 {

 struct flower* tmp = pq.top//;

 pq.pop//; 

 tmp-&gt;visited = true;

 if/!first/

 {

 printf/","/;

 }

 first = false;

 printf/"%d", tmp-&gt;height/;

 for/int j = 0; j &lt; size; j++/

 {

 if/!flowers[j].visited &amp;&amp; partial_order[tmp-&gt;id][j]/

 {

 flowers[j].ind--;

 if/flowers[j].ind == 0/

 {

 pq.push/&amp;flowers[j]/;

 }

 }

 }

 }

 printf/"}\n"/;

}



int main/int argc, char** argv/

{

 int height[] = {5,4,3,2,1};

 int bloom[] = {1,1,1,1,1};

 int wilt[] = {365,365,365,365,365};



 getOrdering/height, bloom, wilt, sizeof/height//sizeof/height[0]//;



 int height0[] = {5,4,3,2,1};

 int bloom0[] = {1,5,10,15,20};

 int wilt0[] = {4,9,14,19,24};



 getOrdering/height0, bloom0, wilt0, sizeof/height0//sizeof/height0[0]//;



 int height1[] = {5,4,3,2,1};

 int bloom1[] = {1,5,10,15,20};

 int wilt1[] = {5,10,15,20,25};



 getOrdering/height1, bloom1, wilt1, sizeof/height1//sizeof/height1[0]//;



 int height2[] = {5,4,3,2,1};

 int bloom2[] = {1,5,10,15,20};

 int wilt2[] = {5,10,14,20,25};



 getOrdering/height2, bloom2, wilt2, sizeof/height2//sizeof/height2[0]//;



 int height3[] = {1,2,3,4,5,6};

 int bloom3[] = {1,3,1,3,1,3};

 int wilt3[] = {2,4,2,4,2,4};



 getOrdering/height3, bloom3, wilt3, sizeof/height3//sizeof/height3[0]//;



 int height4[] = {3,2,5,4};

 int bloom4[] = {1,2,11,10};

 int wilt4[] = {4,3,12,13};



 getOrdering/height4, bloom4, wilt4, sizeof/height4//sizeof/height4[0]//;



}

</struct></queue></vector></stdlib.h></stdio.h>

君笑尘

赞同来自:

与Roba一样，但在 Javascript /ES6/:

function getOrdering/height, bloom, wilt/ {

 var n = height.length;



 var idx = [];

 for /var i = 0; i < n; ++i/ idx[i] = i;



 idx.sort/ /a, b/ => height[a] - height[b] /;



 var intersect = /a, b/ => !/bloom[a] > wilt[b] || bloom[b] > wilt[a]/;



 for /var i = 1; i < n; ++i/ {

 // assume they are ordered correctly till index /i-1/,

 // start moving flower i to the left until it can't move because of intersection

 var j = i, flw = idx[i];

 while /j > 0 && !intersect/idx[j-1], flw// {

 idx[j] = idx[j-1];

 idx[--j] = flw;

 }

 }



 return idx.map/ x => height[x] /;

}

喜特乐

赞同来自:

解决问题的图表算法：

创建面向的图形/V, E/:
V - > 花的类型
E - > 关系之间的关系 2 花的类型

For all pairs /v_i, v_j/

 If v_i is smaller than v_j and v_j 'blocks' v_i

 draw an edge starting from v_i to v_j

For all nodes v_i

 Find the v_i with no incoming edges and the biggest height

 -> write it at the end of the result list

 -> remove v_i and all of its outgoing edges from graph

有关更详细的描述，请查看此论坛：
https://apps.topcoder.com/foru ... 55393

詹大官人

赞同来自:

类似于抢劫，再次 Python 和略微复杂的重叠开花检查/枯萎。

H = 0

B = 1

W = 2



def getOrdering/heights, blooms, wilts/:



 def _f1_after_f2/f1, f2/:

 fs1 = set/range/f1[B], f1[W]+1//

 fs2 = set/range/f2[B], f2[W]+1//

 return f1[H] > f2[H] if fs2.intersection/fs1/ != set/[]/ else False



 fs = zip/heights, blooms, wilts/

 fs.sort//

 ffs = []

 for f1 in fs:

 insert_at = len/ffs/

 for f2 in reversed/ffs/:

 if _f1_after_f2/f1, f2/: break

 insert_at -= 1

 ffs.insert/insert_at, f1/

 return [f[H] for f in ffs]

风见雨下

赞同来自:

洗涤它就像分拣插入物一样。对于每朵新的花，他向前返回并检查它是否不会阻挡他面前的那个; 如果是这样，这意味着他

必须

放在他身后。以同样的方式，他还从前面搜索并检查他的身后是否落后于他; 如果是这样，这意味着他

必须

放在它面前。如果没有块，它只是检查身高的最佳位置。

#include <stdio.h>

#include <stdint.h>

#include <stdlib.h>

#include <stdbool.h>



#define uint32 uint32_t



static void

Swap/int *AIdx, int *BIdx/

{

 int Tmp = *AIdx;

 *AIdx = *BIdx;

 *BIdx = Tmp;

}



static void

SwapTo/int Start, int End, int *Array/

{

 while/Start != End/

 {

 Swap/&amp;Array[Start], &amp;Array[Start - 1]/;

 --Start;

 }

}



static void

PrintTo/int End, int *Array/

{

 for/int Idx = 0;

 Idx &lt; End;

 ++Idx/

 {

 printf/"%d, ", Array[Idx]/;

 }

 printf/"\n"/;

}



/* Does A block B? */

static bool

Blocks/int AIdx, int BIdx, int *Heights, int *Blooms, int *Wilts/

{

 bool Result = /Heights[AIdx] &gt; Heights[BIdx] &amp;&amp;

 Wilts[AIdx] &gt;= Blooms[BIdx] &amp;&amp; 

 Blooms[AIdx] &lt;= Wilts[BIdx]/;



 return Result;

}



static void

Order/int *Heights, int *Blooms, int *Wilts, 

 int FlowerCount/

{

 for/int FlowerIdx = 1;

 FlowerIdx &lt; FlowerCount;

 ++FlowerIdx/

 {

 PrintTo/FlowerIdx, Heights/;



 /* front to back */

 int MinIdx = -1;

 for/int Idx = 0;

 Idx &lt; FlowerIdx;

 ++Idx/

 {

 if/Blocks/Idx, FlowerIdx, Heights, Blooms, Wilts//

 {

 MinIdx = Idx;

 break;

 }

 }



 /* back to front */

 int MaxIdx = -1;

 for/int Idx = /FlowerIdx - 1/;

 Idx &gt;= 0;

 --Idx/

 {

 if/Blocks/FlowerIdx, Idx, Heights, Blooms, Wilts//

 {

 MaxIdx = /Idx + 1/;

 break;

 }

 }



 /* best height index */

 int BestHeightIdx = -1;

 if/MinIdx == -1 &amp;&amp;

 MaxIdx == -1/

 {

 for/int Idx = 0;

 Idx &lt; FlowerIdx;

 ++Idx/

 {

 if/Heights[FlowerIdx] &gt; Heights[Idx]/

 {

 BestHeightIdx = Idx;

 break;

 }

 }



 if/BestHeightIdx == -1/

 {

 BestHeightIdx = FlowerIdx;

 }

 }



 int SwapToIdx = -1;

 if//MaxIdx == -1 &amp;&amp; MinIdx != -1/ ||

 /MinIdx == -1 &amp;&amp; MaxIdx != -1/ ||

 /MaxIdx != -1 &amp;&amp; MinIdx != -1 &amp;&amp; MaxIdx == MinIdx//

 {

 SwapToIdx = /MinIdx != -1/ ? MinIdx : MaxIdx;

 }

 else if/BestHeightIdx != -1/

 {

 SwapToIdx = BestHeightIdx;

 }

 else

 {

 fprintf/stderr, "Spot-finding error:\n MinIdx: %d, MaxIdx: %d, BestHIdx: %d\n",

 MinIdx, MaxIdx, BestHeightIdx/;

 exit/1/;

 }



 SwapTo/FlowerIdx, SwapToIdx, Heights/;

 SwapTo/FlowerIdx, SwapToIdx, Blooms/;

 SwapTo/FlowerIdx, SwapToIdx, Wilts/;

 }

}



int

main/int argc, char *argv[]/

{

 int Heights0[] = {5,4,3,2,1};

 int Blooms0[] = {1,1,1,1,1};

 int Wilts0[] = {365,365,365,365,365};



 int Heights1[] = {5,4,3,2,1};

 int Blooms1[] = {1,5,10,15,20};

 int Wilts1[] = {4,9,14,19,24};



 int Heights2[] = {5,4,3,2,1};

 int Blooms2[] = {1,5,10,15,20};

 int Wilts2[] = {5,10,15,20,25};



 int Heights3[] = {5,4,3,2,1};

 int Blooms3[] = {1,5,10,15,20};

 int Wilts3[] = {5,10,14,20,25};



 int Heights4[] = {1,2,3,4,5,6};

 int Blooms4[] = {1,3,1,3,1,3};

 int Wilts4[] = {2,4,2,4,2,4};



 int Heights5[] = {3,2,5,4};

 int Blooms5[] = {1,2,11,10};

 int Wilts5[] = {4,3,12,13};



 int *AllHeights[] = {Heights0, Heights1, Heights2, Heights3, Heights4, Heights5};

 int *AllBlooms[] = {Blooms0, Blooms1, Blooms2, Blooms3, Blooms4, Blooms5};

 int *AllWilts[] = {Wilts0, Wilts1, Wilts2, Wilts3, Wilts4, Wilts5};

 int AllFlowerCounts[] = {5, 5, 5, 5, 6, 4};



 printf/"\n"/;

 for/int Idx = 0;

 Idx &lt; 6;

 ++Idx/

 {

 int *Heights = AllHeights[Idx];

 int *Blooms = AllBlooms[Idx];

 int *Wilts = AllWilts[Idx];

 int FlowerCount = AllFlowerCounts[Idx];



 printf/"Test %d\n", Idx/;

 Order/Heights, Blooms, Wilts, FlowerCount/;

 printf/"{ "/;

 for/int Idx = 0;

 Idx &lt; FlowerCount;

 ++Idx/

 {

 printf/"%d", Heights[Idx]/;

 if/Idx != /FlowerCount - 1//

 {

 printf/", "/;

 }

 }

 printf/" }\n\n"/;

 }

}

EDIT: 这个解决方案是可怕的，我提出了最好的，这实际上是 DP; 它包括以下内容：对于每朵花，通过所有其他花，检查其中哪一个它;对于那些它块的颜色，检查它块的所有颜色，依此类推，直到您到达没有阻止其他人的花。将这朵花放在一个新的阵列中。回来并将每一花朵放在这个新的肿块的下一个插槽前面。如果您为每种花卉执行此操作，您将获得一个装满颜色的数组，这些颜色不会阻挡其他颜色。然后你把每朵花都放在前面。 DP 其中一些决定是有时你会遇到同一朵花，它已经被另一个花朵被另一个花朵被封锁，并且已经放在一个新的阵列中，所以我们跳过这朵花，而不是追求它阻塞的花朵。
</stdbool.h></stdlib.h></stdint.h></stdio.h>

小明明

赞同来自:

我有一个实现 c++. 我使用了用于分别存储高度，开花和衰落的传染媒介类型，然后将其分类 w.r.t 在高度之后，他接一个地拍摄了鲜花，并按照与他们相关的价值观放置它们。

这是代码 :-

[code]#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

bool comp/pair<int, pair<int,int=""> >& a,pair<int, pair<int,int=""> >& b /{
return /a.first > b.first/;
}

bool justify/pair<int, pair<int,int=""> >& a,pair<int, pair<int,int=""> >& b, int k , int
j, vector<pair<int,pair<int,int> > >& v/{
if///b.second.first <= a.second.first/ && /b.second.second>= a.second.first// ||
//b.second.first <= a.second.second/ && /b.second.second>= a.second.second// ||
//b.second.first > a.second.first/ && /b.second.second < a.second.second/ //{

pair<int, pair<int,int=""> > temp = v[j];
int i = j-1;
while/i >= k/{

v[i+1] = v[i];
i--;

}
v[k] = temp;
return true;
}
return false;
}

int main// {

vector<pair<int,pair<int,int> > > v;
int n,a,b,c;
cin>>n;
for/int i = 0;i < n;i++/{
cin>>a>>b>>c;
v.push_back/make_pair/a,make_pair/b,c///;
}

sort/v.begin//, v.end//, comp/;

for/int j = 1;j < n;j++/{
for/int k = 0;k < j;k++/{
bool res = justify/v[k],v[j], k, j, v/;
if/res/
break;
}
}

cout<<"output"<<endl; "<<v[i].second.first<<"="" "<<v[i].second.second<<endl;="" 0;="" <="" code]="" cout<<v[i].first<<"="" div="" for="" i="0;i" int="" n;i++="" return="" {="" }="" }[="">
</endl;></pair<int,pair<int,int></int,></pair<int,pair<int,int></int,></int,></int,></int,></algorithm></utility></vector></iostream>

要回复问题请先登录或注册

看起来像什么样子 FlowerGarden pr0blem 在 TopCoder a DP-one?

11 个回复

发起人

相关问题

问题状态

看起来像什么样子 FlowerGarden pr0blem 在 TopCoder a DP-one?

与内容相关的链接

11 个回复

发起人

相关问题

问题状态