Redian新闻
>
这里好些高质量的帖子和主题讨论啊
avatar
这里好些高质量的帖子和主题讨论啊# Parenting - 为人父母
g*e
1
给定一个数组, A[ 0 .... N ]作为输入数组。给定一个函数 f(i,j) ,这个函数以两个
下表(i,j) 为输入, 返回一个值。(这个函数是个 blackbox, 唯一的信息就是输入两个
整数返回一个值)。要求把数 组 A 分为 3 份,使得 f(0,a) + f(a,b) + f(b,N)最小。
avatar
y*i
2
YANER TIDEWATER最近都好些不错的
然后今天我考古发现了RAINLION的一系列帖子
很可惜我没有在给孩子找PRE-SCHOOL前都读到啊 可惜
还有谁的帖子大家看过觉得很有质量的 请推荐ID名啊 我要考古去
avatar
s*n
3
数组元素值有用吗?f输入只需要下标0-N,a,b都是下标吧?
avatar
m*k
4
beida101

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

avatar
q*x
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)最小。

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

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

avatar
p*2
7
现在只能想到brute force
avatar
y*i
8
mit有历史了 很多版精华都是08之前update的 所以我都不太看了

★ 发自iPhone App: ChineseWeb 7.7

【在 k******e 的大作中提到】
: 我每进一个新的版面都是先到保留区和精华区瞄两眼
: 有时候收获还8错

avatar
c*1
9
这个题我也碰到过
估计最好的方法就是brute force加
cache一下吧
n^2次调用blackbox是少不了的吧
avatar
k*e
10
MM说的对。所以,看保留区,也时共进。不过有一些东西是不会随时间改变的啊,所以
精华区也看看。呵呵 :)

【在 y****i 的大作中提到】
: mit有历史了 很多版精华都是08之前update的 所以我都不太看了
:
: ★ 发自iPhone App: ChineseWeb 7.7

avatar
p*2
11

看样子没用。
是。

【在 s******n 的大作中提到】
: 数组元素值有用吗?f输入只需要下标0-N,a,b都是下标吧?
avatar
p*2
12

分成三份,应该a
【在 q****x 的大作中提到】
: a < b? 这啥题啊。
avatar
n*w
13
典型的dp。
Generalize这个问题。把n个数divide成k个group。使得和最小。
根据CLRS上的说法,
Complete Choice Property是,最后一个group从哪个index开始。假设从i。
Subproblem变成把前i-1个数divide成k-1个group。
avatar
s*n
14
展开说说?感觉套不上本题

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

avatar
p*2
15

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

【在 s******n 的大作中提到】
: 展开说说?感觉套不上本题
avatar
s*n
16
3个组分别是什么内容?假设下标是a,b

【在 p*****2 的大作中提到】
:
: 这个题不就是分成3个组吗?

avatar
p*2
17

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

【在 s******n 的大作中提到】
: 3个组分别是什么内容?假设下标是a,b
avatar
s*n
18
A的值和f无关,f的输入是下标,把题目里整个A去掉,题目意思也不变

【在 p*****2 的大作中提到】
:
: A[0]-A[a]
: A[a]-A[b]
: A[b]-A[n]

avatar
s*n
19
改了一下去掉了A,和原命题等价
给定N,给定一个函数 f(i,j) ,这个函数以两个下表(i,j) 为输入, 返回一个值。(这
个函数是个 blackbox, 唯一的信息就是输入两个整数返回一个值)。求0~N之间的a, b,
使得 f(0,a) + f(a,b) + f(b,N)最小。
avatar
n*w
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)最小。

avatar
s*n
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=
avatar
g*e
22

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

【在 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=
avatar
p*2
23

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

【在 g*********e 的大作中提到】
:
: nice dp.
: but isn't time complexity O(n2)?

avatar
s*n
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)

avatar
n*w
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)
: 五个值最大的一个。

avatar
s*n
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,

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

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

avatar
s*n
28
DP的O(N^2*K),和纯粹的brutal force排列组合O(N!/K!/(N-K)!)哪个好点?,好难判断
avatar
n*w
29
这么比肯定是前者,好得多。
brute force + cache就是dp。

【在 s******n 的大作中提到】
: DP的O(N^2*K),和纯粹的brutal force排列组合O(N!/K!/(N-K)!)哪个好点?,好难判断
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。