小木棍问题，要求用数据结构与算法处理

如果只是要输出最小装配时间的话，不需要什么数据结构

其实算法很简单：记f(n)为装配n个木棍需要的最小装配时间

w[p], l[p]存储需要装配时间的序列中的最后一个木棍的weight、length（p=0 to n）

有f(1) = 1 (w[0], l[0])即第一根木棍的参数

f(2) = 1(存在一个木棍的weight和length都小于另一个) (w[0], l[0])为质量/长度大的那个

f(2) = 2(不存在) (w[0], l[0]), (w[1], l[1])

f(n) = f(n - 1) (存在i(0<=i<f(n)),使得第n根木棍的长度和质量同时大于或小于(w[i],l[i])

若大于,则(w[i], l[i]) = 第n根木棍的长度和质量

f(n) = f(n - 1) + 1 (不存在上述情况，且此时(w[f(n)], l[f(n)])=第n根木棍的长度和质量)

此算法可以看成是递推吧

代码如下

#include <iostream>

using namespace std

int getAns(int number, int *weight, int *length)

{

int answer = 1

int i, j

int *w = new int [number], *l = new int [number]

bool add_one_min = true

w[0] = weight[0], l[0] = length[0]

for (i = 1i <numberi++)

{

add_one_min = true

for (j = 0j <answer &&add_one_minj++)

{

if (w[j] >weight[i] &&l[j] >length[i])

add_one_min = false

if (w[j] <= weight[i] &&l[j] <= weight[j])

{

w[j] = weight[i]

l[j] = weight[j]

add_one_min = false

}

}

if (add_one_min)

{

w[answer] = weight[i]

l[answer] = length[i]

answer++

}

}

delete []w

delete []l

return answer

}

int main()

{

int number, weight[5000], length[5000]

int i

cin >>number

for (i = 0i <numberi++)

cin >>weight[i] >>length[i]

cout <<getAns(number, weight, length)

return 0

}

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <functional>

using namespace std

int stick[100], n

bool used[100]

/*bool comp(int a, int b)

{

return a >b

} */

//unused:没有使用的棍子的数目

//left:剩下的长度

//len:当前认为的计算的长度

bool dfs(int unused, int left, int len)

{

// 所有的棍子已经用了，且没有剩余的长度,符合搜索条件

if (unused == 0 &&left == 0)

return true

int i

//没有剩下的.则新开一条棍子

if (left == 0)

left = len

//寻找没有使用过的棍子

for (i=0i<n++i)

{

//找到没有用过的,而且长度比left值要小(能够填进去)

if (!used[i] &&stick[i]<=left)

{

//使用当前棍子

used[i] = true

//若在当前情况下能够扩展出正确答案,则返回

if (dfs(unused-1, left-stick[i], len))

//成功搜索,返回

return true

//否则不使用当前的棍子

used[i] = false

//若使用stick[i]不能扩展出正确结果,那么如果stick[i]与left等长,则证明len不可能是正确答案

//若left与len等长,就是没有办法扩展

if (stick[i] == left || left == len)

break

}

}

//经过一轮搜索仍得不到正确答案,则返回false

return false

}

int main()

{

int i, sum

while (scanf("%d", &n) != EOF &&n)

{

sum = 0

for (i=0i<n++i)

{

scanf("%d", &stick[i])

used[i] = false

sum += stick[i]

}

//先进行从大到小排序

sort(stick, stick+n, greater<int>())

//根据题目条件，从小向大寻找

for (i=stick[0]i<=sum++i)

{

//棍子总长被i整除才进行搜索,否则没用

if (sum % i == 0)

{

if (dfs(n, 0, i))

{

printf("%d\n", i)

break

}

}

}

}

return 0

}

需要物品：木棒(Stick)×3 + 蛛丝(String)×3

用途：消耗箭，进行远程攻击。

需要物品：燧石(Flint)×1 + 木棒(Stick)×1 + 羽毛(Feather)×1

用途：消耗品，弓来发射。

Tips：玩家射出的箭矢可以收回，但是发射器(Dispenser)射出的不可以

我的世界弓箭的修复解答：两个弓合成一个弓，这种不太推荐的，不如做把新弓，附魔弓推荐用铁砧修，用工作台会使附魔消失，铁砧修要消耗经验的。

---