c********0
发帖数: 112 | 1 题目如下：
给定一个数组， A[ 0 .... N ]作为输入数组。
给定一个函数 f(i,j) ,这个函数以两个下表(i,j)为输入， 返回一个值。
(这个函数是个blackbox, 唯一的信息就是输入两个整数返回一个值)。要求把数组A分
为3份，使得 f(0,a) + f(a,b) + f(b,N)最小。
我只能想到O(n^2)的方法，调用 N^2/2次 f(i,j)
请大牛解答。。。 | w*******m
发帖数: 27 | | i*******s
发帖数: 558 | 3 not clear to me either. Can you give examples?
【在 c********0 的大作中提到】
: 题目如下：
: 给定一个数组， A[ 0 .... N ]作为输入数组。
: 给定一个函数 f(i,j) ,这个函数以两个下表(i,j)为输入， 返回一个值。
: (这个函数是个blackbox, 唯一的信息就是输入两个整数返回一个值)。要求把数组A分
: 为3份，使得 f(0,a) + f(a,b) + f(b,N)最小。
: 我只能想到O(n^2)的方法，调用 N^2/2次 f(i,j)
: 请大牛解答。。。
| c********0
发帖数: 112 | 4 题目的意思就是 有一个函数f(i,j)，以一段数组的起点和终点的index作为输入，返回
一个值. 然后我们的任务是把这个数组分成三段，让这三段的和尽可能的小 (每一段都
有一个起始和终止的index,所以都对应一个f(i,j)的值 )。
Brute force的解法：
起点设为0，对于任意i
起点设为i 对于任意j （j>i）
计算 S = f(0,i) + f（i,j）+ f(j, N)
记录最小的S，这样调用的N^2次的f(i,j),如果用一个表把f(i,j)记下来可以调用
N^2/2次 但是还是O(N^2) | w*******m
发帖数: 27 | 5 题目里面说数组A啥的反而让人不明白吧
这个函数有啥性质啊，没啥性质貌似只能brutal force吧？f(a,b)这如果可以任意变的
必须全试啊？
楼上的只求了min_f(0,a)和min_f(b,N)? | c********0
发帖数: 112 | 6 就是没有说数组A的性质啊。。。
我还问了 f(a,b)有啥特点 说没有特点。。。
我觉得就是brute force的尝试。。。 没有其他方法了吗
【在 w*******m 的大作中提到】
: 题目里面说数组A啥的反而让人不明白吧
: 这个函数有啥性质啊，没啥性质貌似只能brutal force吧？f(a,b)这如果可以任意变的
: 必须全试啊？
: 楼上的只求了min_f(0,a)和min_f(b,N)?
| e*****e
发帖数: 1275 | 7 俺滴思路就是brute force 算出所有f(i, j)
然后DP
不知道还有其他办法没有 | l*******0
发帖数: 176 | 8
这样做的复杂度那就是n^2?
还有灭有加速的手段呢？
【在 e*****e 的大作中提到】
: 俺滴思路就是brute force 算出所有f(i, j)
: 然后DP
: 不知道还有其他办法没有
| s******c
发帖数: 1920 | 9 能具体说下怎么DP吗？
【在 e*****e 的大作中提到】
: 俺滴思路就是brute force 算出所有f(i, j)
: 然后DP
: 不知道还有其他办法没有
|
|
