Re: [理工] [資結]-交大98-資訊聯招-DS&algo核對
※ 引述《twohsien (twohsien)》之銘言：
: 我覺得6.8不是optimal解耶
: 第一次移走一個vertex的edge數為 2n
: 但第二次就有可能選到同邊或不同邊的
: 選到同邊的話才是optimal 2*2n
: 選到不同邊的時候就變成 2*(2n-1)
: 所以最小的就會變成 2n^2 optimal:(2n)^2
: 是這樣吧?有錯請指正@@"
這題我認為是 2n*(n+1)
原PO認為是2*(n^2)應該是覺得有下列情況:
K(2n, 2n)
n n
---------
n n
但此情況的前一種情況一定是:
K(2n, 2n)
n n+1
---------
n n-1
此時 edge 數是 n*(n-1)+(n+1)*n = 2*(n^2)
edge 數沒有增加 所以應該選擇另一種情況:
K(2n, 2n)
n-1 n+1
---------
n+1 n-1
此時 edge 數是 (n-1)*(n-1)+(n+1)*(n+1) = 2*(n^2)+2
以此類推 得到的答案是 2n*(n+1)
有錯請指正!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.121.101
※ 編輯: feather585 來自: 140.113.121.101 (02/13 23:05)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 9 之 9 篇)：