Posted on 2008-01-06 03:13
oyjpart 閱讀(1748)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
SRM386 DIV1
凌晨1點(diǎn)的比賽 很久沒這么晚敲代碼了
今天為計(jì)算機(jī)原理課程設(shè)計(jì)寫了一天的JFC(Java Swing)的東西 也挺累了
不過很想做題 比賽 就來TC了
250分的題是個(gè)暴力的題。題目我理解了挺久，然后敲出來，發(fā)現(xiàn)自己又理解錯(cuò)了，是一個(gè)子集，不是連續(xù)區(qū)間，改了發(fā)現(xiàn)TZTester自寫的test編譯不過，只好用standard的來Test，又調(diào)了好久，結(jié)果110多分收?qǐng)觯Α?br>
500分的題目是帶幾何背景的DP題。
用k個(gè)凸包覆蓋n(n<=15)個(gè)點(diǎn)，求最小的凸包面積和。
15這個(gè)數(shù)字可能暗示著集合DP。我最后用的預(yù)處理集合的面積，然后對(duì)所有點(diǎn)做優(yōu)化的Dijkstra（有個(gè)把邊縮小的過程）.
沒有敲完（第一題耗時(shí)太多）
可惜自己沒想到，凸包（n點(diǎn)） = （n-2）個(gè)三角形，然后做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~
