这里好些高质量的帖子和主题讨论啊 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Parenting - 为人父母

这里好些高质量的帖子和主题讨论啊

这里好些高质量的帖子和主题讨论啊# Parenting - 为人父母

g*e2012-10-26 07:10

1 楼

给定一个数组, A[ 0 .... N ]作为输入数组。给定一个函数 f(i,j) ,这个函数以两个
下表(i,j) 为输入, 返回一个值。(这个函数是个 blackbox, 唯一的信息就是输入两个
整数返回一个值)。要求把数组 A 分为 3 份,使得 f(0,a) + f(a,b) + f(b,N)最小。

y*i2012-10-26 07:10

2 楼

YANER TIDEWATER最近都好些不错的
然后今天我考古发现了RAINLION的一系列帖子
很可惜我没有在给孩子找PRE-SCHOOL前都读到啊可惜
还有谁的帖子大家看过觉得很有质量的请推荐ID名啊我要考古去

s*n2012-10-26 07:10

3 楼

数组元素值有用吗？f输入只需要下标0-N，a,b都是下标吧？

m*k2012-10-26 07:10

4 楼

beida101

【在 y****i 的大作中提到】

: YANER TIDEWATER最近都好些不错的
: 然后今天我考古发现了RAINLION的一系列帖子
: 很可惜我没有在给孩子找PRE-SCHOOL前都读到啊可惜
: 还有谁的帖子大家看过觉得很有质量的请推荐ID名啊我要考古去

q*x2012-10-26 07:10

5 楼

a < b? 这啥题啊。

【在 g*********e 的大作中提到】

: 给定一个数组, A[ 0 .... N ]作为输入数组。给定一个函数 f(i,j) ,这个函数以两个
: 下表(i,j) 为输入, 返回一个值。(这个函数是个 blackbox, 唯一的信息就是输入两个
: 整数返回一个值)。要求把数组 A 分为 3 份,使得 f(0,a) + f(a,b) + f(b,N)最小。

k*e2012-10-26 07:10

6 楼

我每进一个新的版面都是先到保留区和精华区瞄两眼
有时候收获还8错

【在 y****i 的大作中提到】

p*22012-10-26 07:10

7 楼

现在只能想到brute force

y*i2012-10-26 07:10

8 楼

mit有历史了很多版精华都是08之前update的所以我都不太看了

★ 发自iPhone App: ChineseWeb 7.7

【在 k******e 的大作中提到】

: 我每进一个新的版面都是先到保留区和精华区瞄两眼
: 有时候收获还8错

c*12012-10-26 07:10

9 楼

这个题我也碰到过
估计最好的方法就是brute force加
cache一下吧
n^2次调用blackbox是少不了的吧

k*e2012-10-26 07:10

10 楼

MM说的对。所以，看保留区,也时共进。不过有一些东西是不会随时间改变的啊，所以
精华区也看看。呵呵：)

【在 y****i 的大作中提到】

: mit有历史了很多版精华都是08之前update的所以我都不太看了
:
: ★ 发自iPhone App: ChineseWeb 7.7

p*22012-10-26 07:10

11 楼

看样子没用。
是。

【在 s******n 的大作中提到】

: 数组元素值有用吗？f输入只需要下标0-N，a,b都是下标吧？

p*22012-10-26 07:10

12 楼

分成三份，应该a
【在 q****x 的大作中提到】

: a < b? 这啥题啊。

n*w2012-10-26 07:10

13 楼

典型的dp。
Generalize这个问题。把n个数divide成k个group。使得和最小。
根据CLRS上的说法，
Complete Choice Property是，最后一个group从哪个index开始。假设从i。
Subproblem变成把前i-1个数divide成k-1个group。

s*n2012-10-26 07:10

14 楼

展开说说？感觉套不上本题

【在 n*******w 的大作中提到】

: 典型的dp。
: Generalize这个问题。把n个数divide成k个group。使得和最小。
: 根据CLRS上的说法，
: Complete Choice Property是，最后一个group从哪个index开始。假设从i。
: Subproblem变成把前i-1个数divide成k-1个group。

p*22012-10-26 07:10

15 楼

这个题不就是分成3个组吗？

【在 s******n 的大作中提到】

: 展开说说？感觉套不上本题

s*n2012-10-26 07:10

16 楼

3个组分别是什么内容？假设下标是a,b

【在 p*****2 的大作中提到】

:
: 这个题不就是分成3个组吗？

p*22012-10-26 07:10

17 楼

A[0]-A[a]
A[a]-A[b]
A[b]-A[n]

【在 s******n 的大作中提到】

: 3个组分别是什么内容？假设下标是a,b

s*n2012-10-26 07:10

18 楼

A的值和f无关，f的输入是下标，把题目里整个A去掉，题目意思也不变

【在 p*****2 的大作中提到】

:
: A[0]-A[a]
: A[a]-A[b]
: A[b]-A[n]

s*n2012-10-26 07:10

19 楼

改了一下去掉了A，和原命题等价
给定N，给定一个函数 f(i,j) ,这个函数以两个下表(i,j) 为输入, 返回一个值。(这
个函数是个 blackbox, 唯一的信息就是输入两个整数返回一个值)。求0~N之间的a, b,
使得 f(0,a) + f(a,b) + f(b,N)最小。

n*w2012-10-26 07:10

20 楼

不还是那样做么。
假设a不可以等于b。这个无关紧要，只影响dp的下标，不影响dp的使用。
1）把0到N分成3部分。
那么第三部分b的取值可能性有哪些。b可以取2到N。假设b=j，第三部分为j-N
2）剩下0到j，要分成2部分。

2）是1）的subproblem，所以可以dp。
recurrence是
D（i, k） = min {D(j, k-1) + f(j, i)}
k-1=D（i，k）意思是把0到i分成k部分。
这个题是要得到D（N，3）。需要3N的空间，复杂度O(N)。

b,

【在 s******n 的大作中提到】

: 改了一下去掉了A，和原命题等价
: 给定N，给定一个函数 f(i,j) ,这个函数以两个下表(i,j) 为输入, 返回一个值。(这
: 个函数是个 blackbox, 唯一的信息就是输入两个整数返回一个值)。求0~N之间的a, b,
: 使得 f(0,a) + f(a,b) + f(b,N)最小。

s*n2012-10-26 07:10

21 楼

牛！受教了，推广到一般情况，复杂度O(N*K)

【在 n*******w 的大作中提到】

: 不还是那样做么。
: 假设a不可以等于b。这个无关紧要，只影响dp的下标，不影响dp的使用。
: 1）把0到N分成3部分。
: 那么第三部分b的取值可能性有哪些。b可以取2到N。假设b=j，第三部分为j-N
: 2）剩下0到j，要分成2部分。
:
: 2）是1）的subproblem，所以可以dp。
: recurrence是
: D（i, k） = min {D(j, k-1) + f(j, i)}
: k-1=

g*e2012-10-26 07:10

22 楼

nice dp.
but isn't time complexity O(n2)?

【在 n*******w 的大作中提到】

p*22012-10-26 07:10

23 楼

我也不明白为什么是O(n)

【在 g*********e 的大作中提到】

:
: nice dp.
: but isn't time complexity O(n2)?

s*n2012-10-26 07:10

24 楼

恩，仔细想想，DP似乎无法O(n)，分析如下：
DP特征是多个Stage，本问题是2个stage，N*2的矩阵
stage1第一行a1~an是分2段的最优，计算复杂度为O(N)比较容易理解：ai记住了0到i之
间最小的f(0,j)，j从0到i。所以从左到右随时记住f(0,i)的最小值，一遍扫描就行了。
stage2第二行是b1~bn分3段的最优解
a1 a2 a3 a4 a5
b2 b3 b4 b5
举个例子：b4代表了假设长度为4的时候b应该选0~4某个index，使得f(0,a) + f(a,index) + f(index,4)最大, 可以利用stage 1的结果，就是说查找a(index) + f(index,4)最大的一个，也就是说查找a(1)+f(1,4), a(2)+f(2,4), a(3)+f(3,4)，a(4)+f(4,4)四个值最大的一个。
同理b5是查找a(1)+(f1,5), a(2)+f(2,5), a(3)+f(3,5)，a(4)+f(4,5), a(5)+f(5,5)
五个值最大的一个。
总结是查找bn的时候无法利用b1 ~ bn-1的中间步骤，因为调用的f的第二个参数不同。生成此列花费时间应该是O(n^2)

【在 p*****2 的大作中提到】

:
: 我也不明白为什么是O(n)

n*w2012-10-26 07:10

25 楼

dp里边的重复利用好像不是这个意思。这里肯定是重复利用了。
但是这题跟一般的dp不一样在于，f(a,b)是个未知的。
所以需要先把f(a,b)中a，b各种组合的可能性计算出来保存好。需要O(n^2)的时间。
解D(N,K)的复杂度为O(N^2*K)。

了。
index
4,

【在 s******n 的大作中提到】

: 恩，仔细想想，DP似乎无法O(n)，分析如下：
: DP特征是多个Stage，本问题是2个stage，N*2的矩阵
: stage1第一行a1~an是分2段的最优，计算复杂度为O(N)比较容易理解：ai记住了0到i之
: 间最小的f(0,j)，j从0到i。所以从左到右随时记住f(0,i)的最小值，一遍扫描就行了。
: stage2第二行是b1~bn分3段的最优解
: a1 a2 a3 a4 a5
: b2 b3 b4 b5
: 举个例子：b4代表了假设长度为4的时候b应该选0~4某个index，使得f(0,a) + f(a,index) + f(index,4)最大, 可以利用stage 1的结果，就是说查找a(index) + f(index,4)最大的一个，也就是说查找a(1)+f(1,4), a(2)+f(2,4), a(3)+f(3,4)，a(4)+f(4,4)四个值最大的一个。
: 同理b5是查找a(1)+(f1,5), a(2)+f(2,5), a(3)+f(3,5)，a(4)+f(4,5), a(5)+f(5,5)
: 五个值最大的一个。

s*n2012-10-26 07:10

26 楼

你看我前面的例子分析，应该是O(N^2*K)。具体说吧，本例子里DP里每一个大于1的
Stage都要花O(n^2)。

【在 n*******w 的大作中提到】

: dp里边的重复利用好像不是这个意思。这里肯定是重复利用了。
: 但是这题跟一般的dp不一样在于，f(a,b)是个未知的。
: 所以需要先把f(a,b)中a，b各种组合的可能性计算出来保存好。需要O(n^2)的时间。
: 解D(N,K)的复杂度为O(N^2*K)。
:
: 了。
: index
: 4,

n*w2012-10-26 07:10

27 楼

嗯，的确。这个dp算比较难了。
感觉google都考不到这个难度。
前面提到的brute force + cache就是dp的核心思想。dp本质上还是brute force。

【在 s******n 的大作中提到】

: 你看我前面的例子分析，应该是O(N^2*K)。具体说吧，本例子里DP里每一个大于1的
: Stage都要花O(n^2)。

s*n2012-10-26 07:10

28 楼

DP的O(N^2*K)，和纯粹的brutal force排列组合O(N!/K!/(N-K)!)哪个好点？，好难判断

n*w2012-10-26 07:10

29 楼

这么比肯定是前者，好得多。
brute force + cache就是dp。

【在 s******n 的大作中提到】

: DP的O(N^2*K)，和纯粹的brutal force排列组合O(N!/K!/(N-K)!)哪个好点？，好难判断