姚贝娜全清唱集锦，共43分钟 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>TVChinese - 中文电视

姚贝娜全清唱集锦，共43分钟

姚贝娜全清唱集锦，共43分钟# TVChinese - 中文电视

h*b2015-01-22 08:01

1 楼

You are given an array which consist of number between 0 to 5 digit range.
Write a function which will return true or false, if array can be divided
into 2 half such a that sum of the two half would be equal
这个难道不是np-hard? 请教。

c*d2015-01-22 08:01

2 楼

烂就一个字

y*a2015-01-22 08:01

3 楼

★ 发自iPhone App: ChineseWeb 8.6

l*c2015-01-22 08:01

4 楼

dynamic programming O(n**2)

y*a2015-01-22 08:01

5 楼

这不是天才是什么

★ 发自iPhone App: ChineseWeb 8.6

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

: ★ 发自iPhone App: ChineseWeb 8.6

r*c2015-01-22 08:01

6 楼

are you sure? the key is 0 to 5 digits

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

: dynamic programming O(n**2)

L*e2015-01-22 08:01

7 楼

真是太喜欢唱歌了，只要给机会唱，完全不挑啊，什么情况，什么场合下都唱，而且不
是唱一句两句意思意思而已，大段大段整首整首地唱。。。

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

: 这不是天才是什么
:
: ★ 发自iPhone App: ChineseWeb 8.6

s*n2015-01-22 08:01

8 楼

divided into 2 half 什么意思？是说中间划一刀，左边一半右边一半吗？
如果照这个意思难道不是O(n)吗？
1.从头到尾扫描数组，求和得到S
2.接着从头到尾扫描，每一步计算迄今为止左边数字的和L，if (2*L==S) return true
如果divided into 2 half是说把元素任意分成两堆，那就是背包问题吧。
不管哪种理解，跟between 0 to 5 digit range有什么关系呢？

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

: You are given an array which consist of number between 0 to 5 digit range.
: Write a function which will return true or false, if array can be divided
: into 2 half such a that sum of the two half would be equal
: 这个难道不是np-hard? 请教。

x*g2015-01-22 08:01

9 楼

有天籁嗓音的天才歌手。

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

: 这不是天才是什么
:
: ★ 发自iPhone App: ChineseWeb 8.6

l*c2015-01-22 08:01

10 楼

That's the key
only when fixed range data does dynamic programming apply.
for non fixed range, NP problem

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

: are you sure? the key is 0 to 5 digits

Z*a2015-01-22 08:01

11 楼

...你们姚粉自娱自乐不好么，这年头会唱歌的太多了，你们不要刷屏了好不好
追悼信件开一贴，唱歌又来一贴，从好声音开始你们几个就不停的刷屏，烦死了好不好

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

: 这不是天才是什么
:
: ★ 发自iPhone App: ChineseWeb 8.6

h*b2015-01-22 08:01

12 楼

怎么用DP解？能具体说一下吗？3x

c*a2015-01-22 08:01

13 楼

咬字是一大硬伤。 j,q,x 这几个音发得做作。演唱央视味重，缺乏时尚感和个性，作
品无传唱性。预言一年后基本无人提起。

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

: 这不是天才是什么
:
: ★ 发自iPhone App: ChineseWeb 8.6

c*l2015-01-22 08:01

14 楼

mark

y*a2015-01-22 08:01

15 楼

不想看你就别进来
满版还我歌、何以呢，怎么不见你管

★ 发自iPhone App: ChineseWeb 8.6

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

: ...你们姚粉自娱自乐不好么，这年头会唱歌的太多了，你们不要刷屏了好不好
: 追悼信件开一贴，唱歌又来一贴，从好声音开始你们几个就不停的刷屏，烦死了好不好

s*92015-01-22 08:01

16 楼

http://people.csail.mit.edu/bdean/6.046/dp/ is a good resource for DP.
For this problem, DP complexity is O(n**2 10**k) where k is the number of
digits.
Let the array be a1,...,an
Define p(i,j)=1 if the sum of a subset of a1,...,ai is j. It holds that
p(i,j)=1 if p(i-1,j)=1 or p(i-1, j-ai)=1.
#include
using namespace std;
bool subsum(int a[], int n){
int sum=0;
int minI=0;
for(int i=0;isum+=a[i];
minI=(a[minI]>a[i]?i:minI);
}
if(sum%2==1)

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

y*a2015-01-22 08:01

17 楼

人太实在了

★ 发自iPhone App: ChineseWeb 8.6

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

: 真是太喜欢唱歌了，只要给机会唱，完全不挑啊，什么情况，什么场合下都唱，而且不
: 是唱一句两句意思意思而已，大段大段整首整首地唱。。。