Posted on 2009-02-11 18:27
hello_world 閱讀(1526)
評論(0) 編輯 收藏 引用
題目分類
|
| Bridge |
過橋問題 |
| Saskatchewan |
離散化（geometry） |
| Jolly Jumpers |
水題 |
| Tug of War |
DP |
| Interpreter |
模擬
|
bridge：
http://www.cnblogs.com/drizzlecrj/archive/2007/11/24/931011.html
這篇文章有講解還有配套的題目，我不羅嗦了
Saskatchewan：
我是枚舉每列， 然后計算這一列的面積，再加起來就可以了
一列中，先刪去不在當(dāng)前范圍內(nèi)的邊，再把剩下的邊排序，然后從低到高成對的考慮即可
還有能不用 stl 的就盡量不用，很慢
其實(shí)只要想到離散化就很簡單了~~
Tug of War：
這個題目貌似有很多解法，我是這樣做的：
dp[k][i][j]代表前k個人分成兩邊，其中一邊有i個人重量為j的狀態(tài)是否可以達(dá)到！
那么dp[k][i][j]=true if and only if dp[k-1][i-1][j-H[k]]=true；其中0<=k<=100;0<=i<=50;0<=j<=450*100；在題目給3s的情況下還是可以接受的！第一維只是方便理解，實(shí)現(xiàn)同樣可以不管第一維！只要逆推就好了！
當(dāng)處理完上面以后，假設(shè)n個人的總重量是s，最后只要從dp[n][n/2][0~s]中找到最接近s/2的那個狀態(tài)就好了~
Interpreter：
典型的模擬題目，只要理解了題目意思照著寫就可以了~
這里推薦一個類似的題但是難度可能要大一些：
http://202.120.80.191/problem.php?problemid=1840
題目分類
|
| Freckles |
圖論，最小生成樹 |
| |
|
| Primary Arithmetic |
簡單題 |
| Demerit Points |
模擬 |
| Edit Step Ladders |
DP加二分
|
Demerit Points:
直接按照題目模擬就好了，只是有點(diǎn)繁瑣而已！
Edit Step Ladders：
跟LIS的動態(tài)規(guī)劃一樣，dp[i]表示到前前i個單詞最長的，那么dp[i]=max(dp[j])+1;(0<=j<i,且word[j]可以由規(guī)則變成word[i]);轉(zhuǎn)移的時候我們可以讓word[i]通過規(guī)則生成單詞，看該單詞是否在前面出現(xiàn)過！注意我們沒必要生成所有的單詞，因?yàn)橛行颍覀冎恍枰杀葁ord[i]小的單詞！查單詞的時候可以二分查找！
后面討論說可以nlog(n)的，不過我暫時還沒有想到！