Re: [资工] 离散 103北大资工 鸽笼
楼主: Honor1984 (希望愿望成真) 2017-10-24 16:29:06
※ 引述《q1qip123 (wtlee)》之铭言：
: 想请问 在箭头那一行
: 若是我假设一数列为 2,1,6,7,8,9,10,5,4,3
: 则 I(1)=length('2,6,7,8,9,10')
: D(1)=length('10,5,4,3')
: I(2)=length('1,6,7,8,9,10')
: D(2)=length('10,5,4,3')
: 那我a1跟a2定义出来的数对(I,D)都是（6,4）
: 不就不会产生n^2+1个数对了？
: 谢谢！
![]()
:
: 想请问 在箭头那一行
: 若是我假设一数列为 2,1,6,7,8,9,10,5,4,3
: 则 I(1)=length('2,6,7,8,9,10')
: D(1)=length('10,5,4,3')
: I(2)=length('1,6,7,8,9,10')
: D(2)=length('10,5,4,3')
: 那我a1跟a2定义出来的数对(I,D)都是（6,4）
: 不就不会产生n^2+1个数对了？
: 谢谢！
:
作者: q1qip123 (wtlee) 2017-10-24 17:34:00
我理解错的地方是I_i跟D_i都要包含a_i对吧？那想请问在a_i<a_j时，如果不包含a_j为什么一存在递增数列长度>I_j?
楼主: Honor1984 (希望愿望成真) 2017-10-25 11:00:00
只有两种情况 如果不含a_j的数列I_i比含a_j的少 就选择含a_j的
作者: q1qip123 (wtlee) 2017-10-25 13:53:00
我知道是在讨论包不包含a_j不含a_j的情形 直觉上能接受但是说不含a_j时，则存在I_i>l_j,这个"存在"不太能接受抱歉 ,这好像很trivial，但是转不太过来…
楼主: Honor1984 (希望愿望成真) 2017-10-25 15:28:00
如果不包含a_j的所有递增数列长度 <= I_j，那这些递增数列的长度就不会是I_i，而是包含a_j的数列
作者: q1qip123 (wtlee) 2017-10-25 16:07:00
好 我懂了 感谢！