看起来像什么样子 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, 但这不会导致最高可能的高度将成为花园中的第一个。
已邀请:

郭文康

赞同来自:

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

它也让我尴尬,因为
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=""> &gt;&amp; a,pair<int, pair<int,int=""> &gt;&amp; b /{
return /a.first &gt; b.first/;
}




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

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

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


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




int main// {

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


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



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

cout&lt;&lt;"output"&lt;<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>

要回复问题请先登录注册