看好Motorola Photon， BB Free today - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

看好Motorola Photon， BB Free today

看好Motorola Photon， BB Free today# PDA - 掌中宝

a*02012-12-02 08:12

1 楼

想减肥的人第一个决定往往是：不吃主食。不吃主食就能减肥吗？这是有条件的，要看
你忌掉了主食之外还在吃什么？如果你想用肉或者其他零食来代替主食，你的减肥愿望
就会落空，因为在减肥这件事上，吃肉比吃主食更容易长胖！
主食的主要成分是淀粉，也就是碳水化合物，它是提供我们生命能量的主要来源之
一。碳水化合物吃进去之后，马上就要变成血糖，血糖的作用就是为我们的身体提供能
量。人活着，就算你不运动，卧床，但只要躺在那里喘气，呼吸心跳就都需要能量，血
糖就是保证这些的。我们的食物主要又三大营养元素：碳水化合物，脂肪，蛋白质，其
中，碳水化合物转为血糖的速度最快，所以，人发生低血糖的时候，要么直接吃糖，
要么喝一碗粥，糖和粥都是碳水化合物，从来没有用肉汤治疗低血糖的吧？就是因为含
有脂肪和蛋白质的肉以及肉汤，更容易直接作为脂肪储存起来，而不是转化为血糖供身
体消耗。
对于大部分人来说，用血糖来合成脂肪的效率，比直接用食物中的脂肪来合成
人体脂肪的效率要低，通俗的讲就是：通过吃淀粉之类的食物而长胖，比直接吃脂肪长
胖要慢得多，这就首先打断了“吃主食等于长肉”的等号。
那么，是不是主食就可以放开吃呢？绝对不是。
以前有个故事，一个孩子丧母后父亲娶了个后妈，后妈很坏，不给孩子饱饭吃
，孩子家里是种大蒜的，饿了就只能烤大蒜吃，结果，就靠这些烤熟的大蒜，这个孩子
长得白白胖胖的……这个可能有传说成分的故事，从一个角度提示：任何一种食物只要
吃得过量，都会导致肥胖，因为除了白开水，所有食物都含有热量，热量摄入超过身
体的消耗，就要转化为脂肪储存起来，人就发胖了。
既然是任何一种食物，其中当然也包括主食，因此，虽然吃主食比吃肉在减肥上
更有效果，但想通过吃主食来减肥，还需要给身体消耗脂肪的机会。一旦食物中碳水化
合物不足的时候，血糖相对低的时候，身体就会消耗脂肪来供能，减肥就在此时发生了。
怎样能在吃饱的同时，不让血糖过高呢？就是让你的主食别太精致，因为精致的
主食可以很快地升高血糖甚至产生危及胰岛素功能的“血糖风暴”，也是因为这个原因
，很多营养专家，很少吃精米白面，虽然他们的主食顿顿都吃，但都是“掺了假”的，
比如米饭中加麦片，各种杂粮饭或者粥，馒头和面包也是全麦的，或者用土豆山药芋头
代替一部分的主食，这样做的目的就是，在获得饱腹感的同时，减少主食所含的热量，
掺了假的主食纤维素多，热量小，如果这个时候还可以少吃脂肪，食物提供的血糖和热
量都是欠缺的，为了弥补这样的欠缺，身体就会动员储存的脂肪来供能了，你的减肥效
果就会在不知不觉中产生了。
中医养生在饮食上只有一个准则：粗茶淡饭，翻译成营养学的概念就是，主食多粗
粮，副食少油脂，无论对减
肥还是养生都兼顾到了。

f*i2012-12-02 08:12

2 楼

Given are a set of intervals S = {I1,I2.....In}, each interval have
different positive weight (weight is independent to the interval, there may
be the case that a long interval has a low weight but a short interval has
high weight).
Purpose: Find out a subset of S, say Sub, such that for every interval in S,
there is an interval I in Sub such that they are somehow overlap.
Requirement: the total weight of Sub is minimum.
就是说，找到一部分的interval,使得S内的所有interval和他们（中的某一个interval
）都有交集，并且要求最小的weight
希望大家能够看懂题目，并且给我一点提示，多谢。

m*n2012-12-02 08:12

3 楼

>30 days，发现的时候已经被report给credit bureau了……
不小心miss掉的。一月开始用mint来manage我的卡，唯独忘了把这张卡加进去……后来
就miss了一个statement……求轻拍
给客服打电话，倒是直接就把late fee waive掉了。credit report的事情还得打电话
给credit department，争取remove掉。不知道可能性大不大否，求经验……

h*e2012-12-02 08:12

4 楼

【以下文字转载自 Military 讨论区】
发信人: gc01 (gc01), 信区: Military
标题: 港大千名校友師生悼自由之死 ZT
发信站: BBS 未名空间站 (Fri Aug 26 19:47:30 2011, 美东)
港大校友師生悼大學自由之死
【聯合報╱香港特派員李春／香港報導】
2011.08.27 04:36 am
香港大學校園內昨夜聚集近千名校友和師生，聲討港警在李克強訪港期間的保安安排，
哀悼大學自由之死。
李克強八月十八日到訪港大，當日被警察圍困樓梯間的港大學生李成康發言表示，不能
遺忘「八一八」事件，呼籲尋回港大價值，捍衛自由校園，從而建立民主中國。
有來自大陸、入讀港大新聞系的新生發言，指自己是首次參與這類活動，因為大陸無抗
議及集會自由，到香港可自由上網，令她有解放的感覺，但擔心香港遲早會實施廿三條
，屆時就會無自由。校長徐立之到場發言，並歸納三點，一是副總理李克強參加港大百
周年慶典時的座位安排，承認有需要檢討禮儀的規格；二是活動期間有需要開放和平等
參與，三是關於保安的安排，大學有自主權，保護政要的工作必須與警方配合。

F*P2012-12-02 08:12

5 楼

感觉虽然不是苹果只是摩托罗拉,除了分辨率和视觉效果差一点点,真心觉得想买摩托罗
拉.有键盘,有4G，有摄像，有tv，可以国际通用。可是就是月费好贵阿，为什么会让手
机月费贵一倍。。。

f*t2012-12-02 08:12

6 楼

感觉好难，想了一下，贪心法不对

p*a2012-12-02 08:12

7 楼

就给macy's多打打电话聊聊天套套近乎，说不定可能弄掉……

t*y2012-12-02 08:12

8 楼

Photon 难道不是已经Discontinue的老型号了？

v*a2012-12-02 08:12

9 楼

不好意思，这个算法被证明错误了

F*P2012-12-02 08:12

10 楼

没有啊，现在是photon Q

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

: Photon 难道不是已经Discontinue的老型号了？

H*e2012-12-02 08:12

11 楼

这题目没什么头绪阿

may
S,
interval

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

: Given are a set of intervals S = {I1,I2.....In}, each interval have
: different positive weight (weight is independent to the interval, there may
: be the case that a long interval has a low weight but a short interval has
: high weight).
: Purpose: Find out a subset of S, say Sub, such that for every interval in S,
: there is an interval I in Sub such that they are somehow overlap.
: Requirement: the total weight of Sub is minimum.
: 就是说，找到一部分的interval,使得S内的所有interval和他们（中的某一个interval
: ）都有交集，并且要求最小的weight
: 希望大家能够看懂题目，并且给我一点提示，多谢。

d*g2012-12-02 08:12

12 楼

有4G，有摄像???
难道不是是手机就有吗？
Sprint的4G很慢。绝大多数情况下比att的3G慢，有时比2G还慢。而且Photon已经不能
升级了，而且没有community support，因为用的人实在是太少了。
强烈不建议搞这种小众机型。

【在 F********P 的大作中提到】

: 感觉虽然不是苹果只是摩托罗拉,除了分辨率和视觉效果差一点点,真心觉得想买摩托罗
: 拉.有键盘,有4G，有摄像，有tv，可以国际通用。可是就是月费好贵阿，为什么会让手
: 机月费贵一倍。。。

p*22012-12-02 08:12

13 楼

去年G fail我的就是这题。interviewer说，他最近在facebook上看到一个puzzle很有
意思，就给我出了。出的时候就说greedy不行。

F*P2012-12-02 08:12

14 楼

就是觉得它有个键盘挺方便的。为什么不能升级了？什么是community support？

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

: 有4G，有摄像???
: 难道不是是手机就有吗？
: Sprint的4G很慢。绝大多数情况下比att的3G慢，有时比2G还慢。而且Photon已经不能
: 升级了，而且没有community support，因为用的人实在是太少了。
: 强烈不建议搞这种小众机型。

p*22012-12-02 08:12

15 楼

去年G fail我的就是这题。interviewer说，他最近在facebook上看到一个puzzle很有
意思，就给我出了。出的时候就说greedy不行。

a*a2012-12-02 08:12

16 楼

Moto的机器都像iphone一样支持CDMA和GSM，3G UMTS HSPA+。全世界哪里都能使。

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

C*U2012-12-02 08:12

17 楼

有个想法，但是不知道怎么继续。
把interval看成点，有对应的weight。
如果相交，他们之间就有边。
那么问题就变成查找最小weight的顶点子集使得图里的任何定点都有和这个子集里的点
相邻。
这个和minimum vertex cover问题有点像，但是又不一样。

may
S,
interval

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

F*P2012-12-02 08:12

18 楼

对答。不过在公车上看到一个人上网，的确挺慢。。Free with new line now

l*i2012-12-02 08:12

19 楼

You can look at it as the hitting set problem but that does not help you as
either hitting set or vertex cover is NP-hard.
Some idea like DP should work, although I don't know how to deal with
weights if you do not have all weights being small.

a*a2012-12-02 08:12

20 楼

flash一下转ATT或者straighttalk, verizon的网络就是覆盖范围大，但是速度不怎么
地。

【在 F********P 的大作中提到】

: 对答。不过在公车上看到一个人上网，的确挺慢。。Free with new line now

p*22012-12-02 08:12

21 楼

想起来了，要用divide and conquer, divide的时候要小心。

F*P2012-12-02 08:12

22 楼

但是据说att的plan很不划算..
可惜motorola photon不是给upgrade免费,...否则就买拉

【在 a**a 的大作中提到】

: flash一下转ATT或者straighttalk, verizon的网络就是覆盖范围大，但是速度不怎么
: 地。

q*x2012-12-02 08:12

23 楼

不是因为你题没答上来。

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

: 去年G fail我的就是这题。interviewer说，他最近在facebook上看到一个puzzle很有
: 意思，就给我出了。出的时候就说greedy不行。

v*a2012-12-02 08:12

24 楼

try this:
Format: S, E, Weight
1 10 5
1 3 4
6 7 4

intervals 1

【在 C***U 的大作中提到】

: 有个想法，但是不知道怎么继续。
: 把interval看成点，有对应的weight。
: 如果相交，他们之间就有边。
: 那么问题就变成查找最小weight的顶点子集使得图里的任何定点都有和这个子集里的点
: 相邻。
: 这个和minimum vertex cover问题有点像，但是又不一样。
:
: may
: S,
: interval

b*c2012-12-02 08:12

25 楼

怎么做，怎么做，好难。。。
n大于64我就不会做了，有算法能10秒出结果吗

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

: 想起来了，要用divide and conquer, divide的时候要小心。

b*c2012-12-02 08:12

26 楼

有谁能做出来。。。
我有一个test case
[1,2]
[2,3]
...
[64,65]
weigh随机生成

b*c2012-12-02 08:12

27 楼

再来test case
[1,3]
[2,4]
...
[64,66]
weight rand()

b*c2012-12-02 08:12

28 楼

n多大。。。

a*m2012-12-02 08:12

29 楼

木看懂题目。。。感觉是dp.

w*n2012-12-02 08:12

30 楼

dp, O(n^3) time complexity

may
S,
interval

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

b*c2012-12-02 08:12

31 楼

你能过我的test case吗，说说算法

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

: dp, O(n^3) time complexity
:
: may
: S,
: interval

b*c2012-12-02 08:12

32 楼

甩下一句话就走人了。。。

e*l2012-12-02 08:12

33 楼

看看这个递归的思路
public int FindBest(Interval[] S){
if(S.length=0) return 0;
int[] weight; //weight[i]代表在选定区间i的情况下的最优解
for(int i=0;i//假设选定了S[i]，找到S[i]没有相交的区间的集合R
Interval[] R = {S除去S[i]以及和所有S[i]相交的区间};
weight[i] = S[i].weight + FindBest(R); //递归
}
return MIN(weight);
}
可以用一个HashMap记录计算过的集合。

e*l2012-12-02 08:12

34 楼

如果能估出FindBest(R)的下界，就不必要计算所有的weight[]。
就是说如果选i的话无论如何都不可能比当前最好的还要好，就不继续算i了。
int[] weight;
int minimal=INT_MAX;
for(int i=0;iInterval[] R = {S除去S[i]以及和所有S[i]相交的区间};
if(S[i].weight+MinWeight(R)>minimal) //一个简单的估计
weight[i]=INT_MAX; //不算了
else
weight[i] = S[i].weight + FindBest(R); //递归
minimal=(minimal>weight[i])? weight[i]:minimal;
}
//MinWeight(R)代表R中最小的区间weight

s*n2012-12-02 08:12

35 楼

看看这样行么，O(kn)，k是平均相交的数量：
Interval[] S;
if (S.length<=1) return;
sort(S); // sort by start time of every interval
class IntervalResult {
int index;
int[] intersected;
}
IntervalResult[] result;
result[0]for (int i=1; iint j=result.length-1;
for (; j>=0; j--) {
// 假设result[j]的intersected存在元素不能overlap S[i]就停止loop
if (!(S[i] intersects with all result[j].intersected)) break;
}
bool found=false;
for (int k=j+1; k// 如果S[i]的weight小于k到result结尾的weight之和，则用S[i]替换它们
if (S[i].weight< sum_result_weight(k to result.length-1) ) {
int[] replaced = union(result.intersected from k to end);
replaced = union(replaced, i);
result.remove( k to result.length-1);
result.append({i, replaced});
found = true;
break;
}
}
if (!found) {
// 替换没有发生，要么merge入result[length-1]，要么新加一项
if (S[i] intersect with result[length-1].index))
result[length-1].intersected.append(S[i]);
else result.append({i,{S[i]}});
}
}
return result;

e*l2012-12-02 08:12

36 楼

上面的算法是greedy的吧？能保证找到全局最优吗？

e*l2012-12-02 08:12

37 楼

更正，这个不对。Interval远比vertex特殊，Vertex之间的可以有任意的边。
转换成graph相当于把这个问题一般化了。所以原问题不一定是NPC。
===================
这个想法是对的。如果所有weight想等，那么就是minimum vertex cover，是NP-C问题。
所以说原问题比minimum vertex cover更难，必定不存在多项式时间解法。不然你就NB
大了。
如果一个算法是多项式时间，那么一定不能保证找到全局最优解。

【在 C***U 的大作中提到】

s*n2012-12-02 08:12

38 楼

你来举个反例吧

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

: 上面的算法是greedy的吧？能保证找到全局最优吗？

C*U2012-12-02 08:12

39 楼

try this one
Sort by start times.
Let S(i,j) be the best solution in Ii...In such that, Ii..Ij do not need
to
be covered.
S_{inc}(i,j) is the best solution (above) such that Ii is included
S_{ni}(i,j) ....such that Ii is not included
Let l be the last interval which overlaps with Ii
then S_{inc}(i,j) = wi + S(i+1,k) .....where k is max (j, l)
S_{ni}(i,j) = S(i+1,j) if j >= l
else S_{ni}(i,j) = min_k S_{inc}(k,j) ...such that k ranges (i+1 ...l)

【在 b*****c 的大作中提到】

: 甩下一句话就走人了。。。

e*l2012-12-02 08:12

40 楼

更正，这个不对。Interval远比vertex特殊，Vertex之间的可以有任意的边。
转换成graph相当于把这个问题一般化了。所以原问题不一定是NPC。

题。
NB

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

: 更正，这个不对。Interval远比vertex特殊，Vertex之间的可以有任意的边。
: 转换成graph相当于把这个问题一般化了。所以原问题不一定是NPC。
: ===================
: 这个想法是对的。如果所有weight想等，那么就是minimum vertex cover，是NP-C问题。
: 所以说原问题比minimum vertex cover更难，必定不存在多项式时间解法。不然你就NB
: 大了。
: 如果一个算法是多项式时间，那么一定不能保证找到全局最优解。

C*U2012-12-02 08:12

41 楼

是的原问题就是不是npc的
呵呵

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

: 更正，这个不对。Interval远比vertex特殊，Vertex之间的可以有任意的边。
: 转换成graph相当于把这个问题一般化了。所以原问题不一定是NPC。
:
: 题。
: NB

e*l2012-12-02 08:12

42 楼

有几个地方读起来不是很明白，比如S[i]替换的部分，
我猜大意就是假设前n个区间的问题已经解决了，来了一个新的区间n+1，如何更新解。
如果区间n+1不能被前面的解覆盖，就尝试选中区间n+1，看有没有更好。
首先似乎有些下标的问题，导致这个例子不会发生替换：（区间前面的数字是weight）
2 |-------|
1 |-------|
其次我觉得检查result是否和新区间相交的loop是多余的，因为已经排了序，不存在一
个以上的result[j]及其元素同时和新区间全部相交。否则必定有一个包含了所有其他
的。
如果替换发生了，应该是对的。
但是不发生替换的时候，后面的处理不能保证最优解。比如下面例子
5 |-----------|
3 |-|
10 |----|
前2个区间的最优解的weigh是3，加上第3个区间，最优解是5+3。
但是按照这个算法第3个区间会被加进去。变成3+10。

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

: 你来举个反例吧

e*l2012-12-02 08:12

43 楼

按我的理解，S(i,j) = min [ S_{inc}(i,j), S_{ni}(i,j) ]。
最终是求解 S(0,-1)。
好像也有问题，想想这个情况
w0 |----------|
w1 |--|
w2 |---------|
l=2;
S_{inc}(0,-1) = w0 + S(1,2) = w0; 这个是对的。
S_{ni}(0,-1) = min [S_{inc}(1,-1), S_{inc}(2,-1)]
问题在这，S_{inc}(2,-1) 表示选中了w2，但是w1这个区间被漏掉了。

need

【在 C***U 的大作中提到】

: try this one
: Sort by start times.
: Let S(i,j) be the best solution in Ii...In such that, Ii..Ij do not need
: to
: be covered.
: S_{inc}(i,j) is the best solution (above) such that Ii is included
: S_{ni}(i,j) ....such that Ii is not included
: Let l be the last interval which overlaps with Ii
: then S_{inc}(i,j) = wi + S(i+1,k) .....where k is max (j, l)
: S_{ni}(i,j) = S(i+1,j) if j >= l

s*n2012-12-02 08:12

44 楼

是有问题，第二次存的最优解把第一个元素忘掉了，然后把第三个元素加进去，最优解
应该是第一个元素。好吧，没什么好算法了

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

: 有几个地方读起来不是很明白，比如S[i]替换的部分，
: 我猜大意就是假设前n个区间的问题已经解决了，来了一个新的区间n+1，如何更新解。
: 如果区间n+1不能被前面的解覆盖，就尝试选中区间n+1，看有没有更好。
: 首先似乎有些下标的问题，导致这个例子不会发生替换：（区间前面的数字是weight）
: 2 |-------|
: 1 |-------|
: 其次我觉得检查result是否和新区间相交的loop是多余的，因为已经排了序，不存在一
: 个以上的result[j]及其元素同时和新区间全部相交。否则必定有一个包含了所有其他
: 的。
: 如果替换发生了，应该是对的。

C*U2012-12-02 08:12

45 楼

中文解释之前那个英语的有typo。
假设有n个区间。
第一步，我们对n个区间进行排序，得到排好序的n个区间I_1,...,I_n。
第二步, 我们分析这个问题的optimal substructure。
我们用S(i,j)表示只考虑区间I_i,...,I_n，而且I_i,...,I_j不一定被覆盖到的情况下
的最优解。
我们用S_{包含}(i,j)表示S(i,j)这个解包含I_i的情况，用S_{不包含}(i,j)表示S(i,j
)这个解不包含I_i的情况。
假设I_l是和I_i相交的最后一个区间。
那么我们就有一下几个公式：
公式1:S_{包含}(i,j) = w_i + S(i+1,k)，这里k是j和l的较大者，w_i是I_i的weight。
解释：因为这个解包含区间I_i，所以我们必须要加上他的weight w_i。如果j>=l大的
话，因为我们本身考虑的是S(i,j)，所以我们不用关心I_i,...I_j是否被覆盖了，所以
我们只需要S(i+1,j)。如果j在关心I_i,...,I_l了，
所以我们只需要S(i+1,l).
公式2:S_{不包含}(i,j) = S(i+1,j) 如果 j >= l。
解释：因为这个解不包含I_i，而且j比l大，所以我们可以把S(i+1,j)这个最优解放到I
_i,...,I_n，而且I_i,...,I_j不一定被覆盖到的情况下还是最优解。
公式3：S_{不包含}(i,j) = min_k S_{包含}(k,j)，这里的k可以取(i+1 ...l)中任何
一个，而且l > j。
解释：我们需要的是不包含I_i使得在I_i,...,I_n，而且I_i,...,I_j不一定被覆盖到
的情况下的最优解。因为l > j大，所以我们把I_i扔掉以后，我们需要一些I_i+1...I_
j中的元素来覆盖I_j+1...I_l这些区间，因为区间已经排好序列了。而前面的我们不用
考虑。所以我们考虑包含某个I_k的情况。
这个算法开始的时候我们有S(i,n-1) = w_n 对所有的i。
然后我们往前算。

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

: 是有问题，第二次存的最优解把第一个元素忘掉了，然后把第三个元素加进去，最优解
: 应该是第一个元素。好吧，没什么好算法了

e*l2012-12-02 08:12

46 楼

公式3不成立，看29楼

C*U2012-12-02 08:12

47 楼

我想你理解错了。
S(i,j)的这个最优解是在I_i,...,I_n里面挑出来的。不能从前面挑的。
所以29楼那种情况I_1不在I_2,I_3里面。
所以不会选I_1

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

: 公式3不成立，看29楼

e*l2012-12-02 08:12

48 楼

原来是是从后往前算吗？那最终的目标是S(0,0)吗？
S怎么更新的？是S{包含}和S{不包含}较小的那个吗?
对公式3的问题是，S_{包含}(k,j)必须要覆盖 I_j+1, ..., I_l这些区间。
但只选中一个I_k不一定能覆盖 I_j+1, ..., I_l这些区间，虽然这些区间都和I_i相交。
现在明白了，S_{包含}(k,j)并不表示只选一个I_k。

【在 C***U 的大作中提到】

: 我想你理解错了。
: S(i,j)的这个最优解是在I_i,...,I_n里面挑出来的。不能从前面挑的。
: 所以29楼那种情况I_1不在I_2,I_3里面。
: 所以不会选I_1

C*U2012-12-02 08:12

49 楼

对的。
从后往前走。
开始的时候S(i,n-1)都是知道的。就是w_n。
S就是包含和不包含中较小那个。
我是说你理解错了S(i,j)的含义。

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

: 原来是是从后往前算吗？那最终的目标是S(0,0)吗？
: S怎么更新的？是S{包含}和S{不包含}较小的那个吗?
: 对公式3的问题是，S_{包含}(k,j)必须要覆盖 I_j+1, ..., I_l这些区间。
: 但只选中一个I_k不一定能覆盖 I_j+1, ..., I_l这些区间，虽然这些区间都和I_i相交。
: 现在明白了，S_{包含}(k,j)并不表示只选一个I_k。

C*U2012-12-02 08:12

50 楼

对
我刚想给你打最后那句话
可以包含多个
但是肯定包含I_k
所以就没问题了吧？

交。

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

e*l2012-12-02 08:12

51 楼

还有，
公式2为什么不考虑I_i必须被覆盖？
初始化不对，不一定是最后一个。
改了后应该是个好解法

【在 C***U 的大作中提到】

: 对
: 我刚想给你打最后那句话
: 可以包含多个
: 但是肯定包含I_k
: 所以就没问题了吧？
:
: 交。

s*a2012-12-02 08:12

52 楼

你只说明了 S(i,j) 中的 i 怎么往前走，还没说 j怎么往前走呢

C*U2012-12-02 08:12

53 楼

初始化是S(n,n-1)=w_n
赫赫

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

: 还有，
: 公式2为什么不考虑I_i必须被覆盖？
: 初始化不对，不一定是最后一个。
: 改了后应该是个好解法

s*a2012-12-02 08:12

54 楼

初始化应该是 S(n,1), S(n,2) ... S(n, n) 吧
有的是 w_n, 有的是 INF

e*l2012-12-02 08:12

55 楼

if x>y, S(x,y) 没有意义。因为不能保证[y,x]之间的元素被覆盖。
if l>y, S_include(i,y)=S_include(i,l)。 l是和区间i相交的最后的位置。
这样就包含了j往前走。

e*l2012-12-02 08:12

56 楼

但是，我认为只有公式1和3，公式2不应该存在。
S{i,j} = min { S_{包含}(i,j), S_{不包含}(i,j)} 不准确。
应该是
S{i,j} = min { S_{包含}(i,j), S_{不包含i但是覆盖i}(i,j)} 。
这样公式2就不成立了。
解可以不包含i，但是必须覆盖i。S(i+1,j)不能保证这一点。

C*U2012-12-02 08:12

57 楼

你还是没理解对S(i,j)的定义
呵呵
S(i,j)是不用覆盖I_i...I_j的

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

: 但是，我认为只有公式1和3，公式2不应该存在。
: S{i,j} = min { S_{包含}(i,j), S_{不包含}(i,j)} 不准确。
: 应该是
: S{i,j} = min { S_{包含}(i,j), S_{不包含i但是覆盖i}(i,j)} 。
: 这样公式2就不成立了。
: 解可以不包含i，但是必须覆盖i。S(i+1,j)不能保证这一点。