看板 [ Prob_Solve ]
討論串[問題] 一題greedy (codeforces #451 pD)
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 一題greedy (codeforces #451 pD)
推噓1(1推 0噓 2→)留言3則，0人參與, 6年前最新作者GYLin (Lynx)時間6年前 (2018/01/30 22:21), 6年前編輯資訊
2
0
1
內容預覽:
問題連結:. http://codeforces.com/contest/898/problem/D. 大意如下:. 給定一個沒排序過, 互不相同的n個座標(範圍1~10^6),. 將旗子放在這些坐標上,. 再給定m, k兩個數字,. 範圍為:. n >= k >= 1,. m >= 1. 在任意連
(還有579個字)
#2
Re: [問題] 一題greedy (codeforces #451 pD)
推噓1(1推 0噓 2→)留言3則，0人參與, 6年前最新作者ckc1ark (偽物)時間6年前 (2018/01/30 23:33), 6年前編輯資訊
0
0
1
內容預覽:
試著證明看看. greedy的證明蠻多是像這樣證的. 先假設存在某個最佳解 然後在轉換成這個greedy解的過程中不會更糟. 代表greedy解和這個最佳解一樣好. 假設這個greedy解是a0, a1, a2, .... a{n-1} 其中ak=1代表第k個旗子要留 ak=0代表要拆. 如果存在某
(還有385個字)
#3
Re: [問題] 一題greedy (codeforces #451 pD)
推噓0(0推 0噓 1→)留言1則，0人參與, 6年前最新作者outofyou時間6年前 (2018/01/31 21:28), 編輯資訊
0
0
1
內容預覽:
令最佳解中座標最小的旗座標為a[i_1]!=a[0]，. 則最佳解=a[i]+可容下旗座標a[i_1]的最佳解(a[i_1]+m以後)。. 但是因為a[0]<a[i_1]，所以必存在最佳解a[0]+可容下旗座標a[i_1]的最佳解(a[i_1]+m. 以後)。. 用數學歸納法：. 取某座標x小於等於
(還有22個字)
首頁
上一頁
1
下一頁
尾頁