9.26新鲜热乎的狗狗昂塞

xplorld 发表于 2018-10-3 13:51
请问第四题题号多少？谢谢！

694 zszszszs

ErgodicFrog 发表于 2018-10-2 16:41
第一题 01背包  
第二题  meeting room 类似 直接对时间排序（需要标记一下起点，终点和对应的原index）找 ...

请问第一题为啥是01背包问题? 不是all subset吗..

DylanZhang 发表于 2018-10-4 04:06
请问第一题为啥是01背包问题? 不是all subset吗..

数组中的元素可以取或者不取  元素和的range是[0, sum]  
另外你第二题的做法好像有瑕疵，出了考虑kth end time 是不是还要考虑(n -k)th start time

ErgodicFrog 发表于 2018-10-4 04:25
数组中的元素可以取或者不取  元素和的range是[0, sum]  
另外你第二题的做法好像有瑕疵，出了考虑kth e ...

对哦，好像应找kth smallest start time 还有kth smallest end time，
所有和这个区间有交集的都可能。

DylanZhang 发表于 2018-10-4 06:45
对哦，好像应找kth smallest start time 还有kth smallest end time，
所有和这个区间有交集的都可能。

感觉可以之间用math.max(user[i].start, userk.start) < math.min(user[i].end,  userk.end) 来判断是否重叠

2.  好像是segment tree 的模板题。

第二题有对应的题号吗

第一题感觉可以用dp: dp[sum] 表示这个sum是否能够被凑出来，然后我们只需要看dp[sum-1],dp[sum-2], dp[sum-5]是否是true就行了

hdfaji 发表于 2018-10-4 23:30
第一题感觉可以用dp: dp[sum] 表示这个sum是否能够被凑出来，然后我们只需要看dp[sum-1],dp[sum-2], dp[sum ...

这样好像同一个数可能被sum 两次，比如 4本来是算不出来的。但是2,可以算出来，4-2 = 2（true），结果4 也被算出来了