Posted on 2008-01-06 03:13
oyjpart 閱讀(1752)
評論(2) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
SRM386 DIV1
凌晨1點的比賽 很久沒這么晚敲代碼了
今天為計算機原理課程設(shè)計寫了一天的JFC(Java Swing)的東西 也挺累了
不過很想做題 比賽 就來TC了
250分的題是個暴力的題。題目我理解了挺久，然后敲出來，發(fā)現(xiàn)自己又理解錯了，是一個子集，不是連續(xù)區(qū)間，改了發(fā)現(xiàn)TZTester自寫的test編譯不過，只好用standard的來Test，又調(diào)了好久，結(jié)果110多分收場，唉。
500分的題目是帶幾何背景的DP題。
用k個凸包覆蓋n(n<=15)個點，求最小的凸包面積和。
15這個數(shù)字可能暗示著集合DP。我最后用的預(yù)處理集合的面積，然后對所有點做優(yōu)化的Dijkstra（有個把邊縮小的過程）.
沒有敲完（第一題耗時太多）
可惜自己沒想到，凸包（n點） = （n-2）個三角形，然后做DP就可以了。
1000分的題MS只有ACRush 搞定了，我就不看了，睡覺去。。
唉 又要降Rating了
下次好好做。。恩。。
User name: alpc12
Rating (highest): 1466 (1523)
Rated events: 2
Last event: Jan 5, 2008
Member since: Jul 2, 2007
Country: China
Coder type: Student
School: National University of Defense Technology
Default language: C++
Quote: i love MM~
