a*i
2 楼
【 以下文字转载自 Living 讨论区 】
发信人: anweiwei (谁是我是谁), 信区: Living
标 题: 猫抓沙发,请教沙发翻新的问题
发信站: BBS 未名空间站 (Mon Jun 7 11:36:32 2010, 美东)
我家沙发没买多长时间，因为布料没有挑选恰当，现在沙发边缘的地方已经被我家猫猫
抓得惨不忍睹了。
我不知道纽约或者新泽西地区有没有类似的沙发翻新服务，就是可以沙发整个换一种布
料? 谁如果知道,麻烦推荐一下.
不胜感激!
发信人: anweiwei (谁是我是谁), 信区: Living
标 题: 猫抓沙发,请教沙发翻新的问题
发信站: BBS 未名空间站 (Mon Jun 7 11:36:32 2010, 美东)
我家沙发没买多长时间，因为布料没有挑选恰当，现在沙发边缘的地方已经被我家猫猫
抓得惨不忍睹了。
我不知道纽约或者新泽西地区有没有类似的沙发翻新服务，就是可以沙发整个换一种布
料? 谁如果知道,麻烦推荐一下.
不胜感激!
a*7
3 楼
是不是上课很累啊
l*a
4 楼
还有什么条件吗？
每次允许取的值有没有什么限制
【在 d********w 的大作中提到】
: 2个人从一个双向管道中去金币，他们能看到所有的金币面值，但是每次只能从头部或
: 者尾部取，如果让你先取，如何才能取到总和最多的金币
每次允许取的值有没有什么限制
【在 d********w 的大作中提到】
: 2个人从一个双向管道中去金币，他们能看到所有的金币面值，但是每次只能从头部或
: 者尾部取，如果让你先取，如何才能取到总和最多的金币
u*g
5 楼
帮顶，同时请教如何让猫不抓沙发？？？
s*g
6 楼
律师有赚钱多的,也有落魄赚钱少的.(现在law school毕业的大概找到工作的在~50%??
自己去查吧)
专利律师也要写作好的.
(一般律师的话,能说违心话吗?能,就去!)
但也有转专利律师干的好的,人际交往/写作都要棒!
自己去查吧)
专利律师也要写作好的.
(一般律师的话,能说违心话吗?能,就去!)
但也有转专利律师干的好的,人际交往/写作都要棒!
i*d
7 楼
DP
max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
如果只是以拿得比对方多为目的，就简单一些
如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
如果n是奇数，要多算一步
【在 d********w 的大作中提到】
: 2个人从一个双向管道中去金币，他们能看到所有的金币面值，但是每次只能从头部或
: 者尾部取，如果让你先取，如何才能取到总和最多的金币
max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
如果只是以拿得比对方多为目的，就简单一些
如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
如果n是奇数，要多算一步
【在 d********w 的大作中提到】
: 2个人从一个双向管道中去金币，他们能看到所有的金币面值，但是每次只能从头部或
: 者尾部取，如果让你先取，如何才能取到总和最多的金币
p*f
8 楼
沙发边上放一个让她更喜欢磨爪的东西。
【在 u********g 的大作中提到】
: 帮顶，同时请教如何让猫不抓沙发？？？
【在 u********g 的大作中提到】
: 帮顶，同时请教如何让猫不抓沙发？？？
h*t
9 楼
来不及了，除非你对美国政治历史海洋法系法理有足够的基础。
否则，想都别想
否则，想都别想
t*d
10 楼
啥意思？有多少取多少，拿光了不就最多了吗。
a*y
12 楼
两个人轮着拿吧
【在 t**d 的大作中提到】
: 啥意思？有多少取多少，拿光了不就最多了吗。
【在 t**d 的大作中提到】
: 啥意思？有多少取多少，拿光了不就最多了吗。
b*s
13 楼
嗯，dp
l*a
14 楼
求解释。
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
n*y
15 楼
假定知道了max[2,n]和max[1,n-1]
取 a[1] + max[2,n] 和 max[1, n -1] + a[n] 中较大的那个
（这是从头取） 或者 （从另外一边取）
取 a[1] + max[2,n] 和 max[1, n -1] + a[n] 中较大的那个
（这是从头取） 或者 （从另外一边取）
d*2
16 楼
Can you explain what a[1~n] means? If it is sum, does not look right.
On the other hand, your non-DP algo (i.e. 如果只是以拿得比对方多为目的，就简
单一些...) seems to be the right answer, considering your opponent is trying
to max his return.
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
On the other hand, your non-DP algo (i.e. 如果只是以拿得比对方多为目的，就简
单一些...) seems to be the right answer, considering your opponent is trying
to max his return.
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
h*k
17 楼
似乎不对，你取完了就是对方取了。所以假设max[i,j]是还剩下i,...,j个金币时，能
拿到的最优解，即所能拿到的最多面值；
sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
结束条件max(i,i+1) = max(a(i),a(i+1))
【在 n********y 的大作中提到】
: 假定知道了max[2,n]和max[1,n-1]
: 取 a[1] + max[2,n] 和 max[1, n -1] + a[n] 中较大的那个
: （这是从头取） 或者 （从另外一边取）
拿到的最优解，即所能拿到的最多面值；
sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
结束条件max(i,i+1) = max(a(i),a(i+1))
【在 n********y 的大作中提到】
: 假定知道了max[2,n]和max[1,n-1]
: 取 a[1] + max[2,n] 和 max[1, n -1] + a[n] 中较大的那个
: （这是从头取） 或者 （从另外一边取）
l*c
18 楼
ibread是对的.
a[1~n]是所有金币的总和. a[1~n]-max[2,n]就是你取a[1],你的对手只能取剩下的.
a[1~n]-max[1,n-1]就是你取走a[n].
偶数个金币的排列肯定是
奇偶奇偶。。。。。奇偶
你选了奇/偶的金币，对手只能选偶/奇的。所以可以用这个简单的策略。
类似上面的方法可以决定最佳方法，不过没有办法保证比对方拿的多
a[1~n]是所有金币的总和. a[1~n]-max[2,n]就是你取a[1],你的对手只能取剩下的.
a[1~n]-max[1,n-1]就是你取走a[n].
偶数个金币的排列肯定是
奇偶奇偶。。。。。奇偶
你选了奇/偶的金币，对手只能选偶/奇的。所以可以用这个简单的策略。
类似上面的方法可以决定最佳方法，不过没有办法保证比对方拿的多
n*y
19 楼
或者写成下面这样子更好理解一点
a[1] + max[3, n]
a[1] + max[2, n-1]
max [1,n] = max a[n] + max[1, n-2]
a[n] + max[2, n-1]
【在 h**k 的大作中提到】
: 似乎不对，你取完了就是对方取了。所以假设max[i,j]是还剩下i,...,j个金币时，能
: 拿到的最优解，即所能拿到的最多面值；
: sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
: max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
: 结束条件max(i,i+1) = max(a(i),a(i+1))
a[1] + max[3, n]
a[1] + max[2, n-1]
max [1,n] = max a[n] + max[1, n-2]
a[n] + max[2, n-1]
【在 h**k 的大作中提到】
: 似乎不对，你取完了就是对方取了。所以假设max[i,j]是还剩下i,...,j个金币时，能
: 拿到的最优解，即所能拿到的最多面值；
: sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
: max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
: 结束条件max(i,i+1) = max(a(i),a(i+1))
h*g
20 楼
请问为什么要分奇数和偶数来算啊？
为什么奇数要多算一步啊
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
为什么奇数要多算一步啊
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
i*e
21 楼
我的公式是：
i from 1 to n
j from i to n
max(i,j) = A[i], when i = j,
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1)), when i != j
max coins get by player 1 = max(1,n)
这公式跟你是一样的吧？(a(i)+sum(i+1,j) = sum(i,j))
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 h**k 的大作中提到】
: 似乎不对，你取完了就是对方取了。所以假设max[i,j]是还剩下i,...,j个金币时，能
: 拿到的最优解，即所能拿到的最多面值；
: sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
: max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
: 结束条件max(i,i+1) = max(a(i),a(i+1))
i from 1 to n
j from i to n
max(i,j) = A[i], when i = j,
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1)), when i != j
max coins get by player 1 = max(1,n)
这公式跟你是一样的吧？(a(i)+sum(i+1,j) = sum(i,j))
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 h**k 的大作中提到】
: 似乎不对，你取完了就是对方取了。所以假设max[i,j]是还剩下i,...,j个金币时，能
: 拿到的最优解，即所能拿到的最多面值；
: sum(i,j)是从第i个到第j个金币的总面值。递归条件如下
: max(i,j)= max(a(i)+sum(i+1,j)-max(i+1,j), a(j)+sum(i,j-1)-max(i,j-1))
: 结束条件max(i,i+1) = max(a(i),a(i+1))
i*e
22 楼
如果硬币个数为偶数的话，就如 lilacc 和 ibread 所说的，只要比较奇数位置硬币之
和，还有偶数硬币之和就可以了。这是因为硬币个数为偶数时，先走的能够确保对手拿
所有奇数（或是偶数）位置的硬币。
打个比方，如果总共有10枚硬币。我先拿位置 1 的硬币，那对手就必须选择位置 2 或
者 10 的硬币。如果我先拿位置 10 的硬币，对手只能选择位置 1 或 9 的硬币。在硬
币个数为偶数时，这样的策略能保证对手拿的硬币位置全是偶数（或奇数），因此先拿
的绝对不会输。
如果硬币个数为奇数的话，那就要多算一步。假设对手也聪明，利用以上的策略，那就
可以准确预测对手下一步会拿那一枚硬币。这样就只需要算多一步。这时候，先拿的未
必会赢。
哦，明白了，dp 公式算的是 maximum possible amount，这里指的是对手拿硬币不一定根据以上的策略。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
和，还有偶数硬币之和就可以了。这是因为硬币个数为偶数时，先走的能够确保对手拿
所有奇数（或是偶数）位置的硬币。
打个比方，如果总共有10枚硬币。我先拿位置 1 的硬币，那对手就必须选择位置 2 或
者 10 的硬币。如果我先拿位置 10 的硬币，对手只能选择位置 1 或 9 的硬币。在硬
币个数为偶数时，这样的策略能保证对手拿的硬币位置全是偶数（或奇数），因此先拿
的绝对不会输。
如果硬币个数为奇数的话，那就要多算一步。假设对手也聪明，利用以上的策略，那就
可以准确预测对手下一步会拿那一枚硬币。这样就只需要算多一步。这时候，先拿的未
必会赢。
哦，明白了，dp 公式算的是 maximum possible amount，这里指的是对手拿硬币不一定根据以上的策略。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
i*e
23 楼
你这 dp 公式跟我是一样的：
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1))，
然后 base case 为 max(i, j) = A[i], when i == j
可以用递归两行代码搞定，如果要提高效率的话用二维数组当缓冲，以免重复计算。
其实根本不需要这个公式来计算，直接计算硬币偶数位置的和，还有硬币奇数位置的和
，哪一个大就是答案了。（如果硬币个数是奇数的话，算多一步就知道答案了）。这是
因为对手也是聪明的，那他也会用同样的策略，所以对手的每一步都是可以预知的，所
以不需要 dp 公式来计算。
那如果把问题换为：
我先拿硬币，假设对手非常笨（尽量使得我拿到最多的硬币总值），那我最多能拿多少
呢？
这问题就要用 dp 来解了。
大家来探讨下思路吧。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1))，
然后 base case 为 max(i, j) = A[i], when i == j
可以用递归两行代码搞定，如果要提高效率的话用二维数组当缓冲，以免重复计算。
其实根本不需要这个公式来计算，直接计算硬币偶数位置的和，还有硬币奇数位置的和
，哪一个大就是答案了。（如果硬币个数是奇数的话，算多一步就知道答案了）。这是
因为对手也是聪明的，那他也会用同样的策略，所以对手的每一步都是可以预知的，所
以不需要 dp 公式来计算。
那如果把问题换为：
我先拿硬币，假设对手非常笨（尽量使得我拿到最多的硬币总值），那我最多能拿多少
呢？
这问题就要用 dp 来解了。
大家来探讨下思路吧。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 i****d 的大作中提到】
: DP
: max[1,n] = max{a[1~n]-max[2,n], a[1~n]-max[1,n-1]}
: 如果只是以拿得比对方多为目的，就简单一些
: 如果n是偶数，算下奇数位置金币和，以及偶数位置金币和，看哪个多就可以决策了
: 如果n是奇数，要多算一步
i*e
24 楼
终于把这题研究明白了，而且找到自己错在哪里，希望以下的总结对各位有帮助.
的和，哪一个大就是答案了。
刚刚发现一个 counter example 证明以上的说法是错的.
举例：
{3,2,2,3,1,2}
这时候第一个拿硬币的人最多可以拿到 8 的总值。（不管对手采取什么策略）
第一步拿左 3，这时候对手可以选择拿左 2 或右 2.
-- 如果对手拿左 2，我就拿右 2，剩下 {2,3,1}. 最后的 3 我是吃定的了。总值
为 8.
-- 如果对手拿右 2，我就拿左 2，剩下 {2,3,1}. 最后的 3 我也是吃定了。总值
也为 8.
所以，不管对手采取什么策略，我都能保证我最多能拿 8（假设对手是聪明的）.
如果算偶数位置的总值（7）和奇数位置的总值（6），这样虽然获胜，但不能保证能拿
到最大的硬币总值。当硬币个数为偶数时，这策略能保证绝对不输（但有可能打平）
但是，当硬币个数为奇数的时候就不能用以上的策略。当我拿了第一枚硬币之后，硬币
个数就成为偶数了。对手并不一定会使用以上的策略。所以，要寻找你所能拿到最大的
硬币总值，必须使用 DP 来解。
公式为：(where P(i,j) denotes the maximum amount of coins you can get
between location i and j (inclusive))
P(i,j) = max{ sum(i,j)-P(i+1,j), sum(i,j)-P(i,j-1) }，
可以把以上公式简化为：
P(i,j) = sum(i,j) - min{ P(i+1,j), P(i,j-1) },
P(i,i) = A[i] as base case.
另一个思路（不需要计算 sum(i,j)）的 DP 公式为：
P(i,j) = max{ A[i] + min{ P(i+2,j), P(i+1,j-1) },
A[j] + min{ P(i,j-2), P(i+1,j-1) } }
P(i,i) = A[i] as base case.
以上思路讲解请参考：
http://people.csail.mit.edu/bdean/6.046/dp/
如果把问题转换为对手非常笨的话，使得你最后能拿最大的总值，把上面的 DP 公式换
一换就行了：
P(i,j) = max{ A[i] + max{ P(i+2,j), P(i+1,j-1) },
A[j] + max{ P(i,j-2), P(i+1,j-1) } }
P(i,i) = A[i] as base case.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
的和，哪一个大就是答案了。
刚刚发现一个 counter example 证明以上的说法是错的.
举例：
{3,2,2,3,1,2}
这时候第一个拿硬币的人最多可以拿到 8 的总值。（不管对手采取什么策略）
第一步拿左 3，这时候对手可以选择拿左 2 或右 2.
-- 如果对手拿左 2，我就拿右 2，剩下 {2,3,1}. 最后的 3 我是吃定的了。总值
为 8.
-- 如果对手拿右 2，我就拿左 2，剩下 {2,3,1}. 最后的 3 我也是吃定了。总值
也为 8.
所以，不管对手采取什么策略，我都能保证我最多能拿 8（假设对手是聪明的）.
如果算偶数位置的总值（7）和奇数位置的总值（6），这样虽然获胜，但不能保证能拿
到最大的硬币总值。当硬币个数为偶数时，这策略能保证绝对不输（但有可能打平）
但是，当硬币个数为奇数的时候就不能用以上的策略。当我拿了第一枚硬币之后，硬币
个数就成为偶数了。对手并不一定会使用以上的策略。所以，要寻找你所能拿到最大的
硬币总值，必须使用 DP 来解。
公式为：(where P(i,j) denotes the maximum amount of coins you can get
between location i and j (inclusive))
P(i,j) = max{ sum(i,j)-P(i+1,j), sum(i,j)-P(i,j-1) }，
可以把以上公式简化为：
P(i,j) = sum(i,j) - min{ P(i+1,j), P(i,j-1) },
P(i,i) = A[i] as base case.
另一个思路（不需要计算 sum(i,j)）的 DP 公式为：
P(i,j) = max{ A[i] + min{ P(i+2,j), P(i+1,j-1) },
A[j] + min{ P(i,j-2), P(i+1,j-1) } }
P(i,i) = A[i] as base case.
以上思路讲解请参考：
http://people.csail.mit.edu/bdean/6.046/dp/
如果把问题转换为对手非常笨的话，使得你最后能拿最大的总值，把上面的 DP 公式换
一换就行了：
P(i,j) = max{ A[i] + max{ P(i+2,j), P(i+1,j-1) },
A[j] + max{ P(i,j-2), P(i+1,j-1) } }
P(i,i) = A[i] as base case.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
相关阅读
转基因绿色鸡可以订购了现实生活里，我是一个窝囊的女人。PI 与博士后的五个层次及各层次中的关系请教几个用来产生 membrane proteins设备的价格 (转载)求文献千老转行求建议zt请给建议！回国申请千青还是继续留在美国？(ZZ)大家对基因组（genome engineering）工程怎么看？University of Alberta来自大陆的叫兽和他老婆犯大事了南京师范大学生科院招聘科研助手傅萍： 3D打印肉给发展中国家(ZT) (转载)这个值得关注吗？Brain Activity MapReport on Science showing impact of one-child policy on individuals in Chinalowess normalization in R请教转基因动物模型成功筛选出临床上用的药物if sequestration happens, NCI budget will be cut 6%求助：关于推荐信被人要reagent的人烦死了貌似又被老板给晃点了一事不解，生物信息学的AP才10万刀，还干个屁？