?這是第二次模擬測試的解題報告
本次題目出自OIBH模擬賽

題目如下：
===================================================================================================================
飲食問題
（eatpuz.pas/c/cpp/in/out）
時限:1 sec | 內存: 64 MB

背景
???? 平平正在減肥，所以要控制他的飲食。并且要求她及時去公園里面散步。
題目描述
平平正在減肥，所以她規定每天不能吃超過 C (10 <= C <= 35,000)卡路里的食物。農民 John 在戲弄她，在她面前放了B (1 <= B <= 21) 捅食物。每桶內都有某個單位卡路里(范圍：1..35,000)的食物(不一定相同)。平平沒有自控能力，一旦她開始吃一個桶中的食物，她就一定把這桶食物全部吃完。
平平對于組合數學不大在行。請確定一個最優組合，使得可以得到最多的卡路里，并且總量不超過C。
例如，總量上限是40卡路里， 6 桶食物分別含有7, 13, 17, 19, 29, 和 31卡路里的食物。平平可以吃7 + 31 = 38卡路里，但是可以獲取得更多： 7 + 13 + 19 = 39卡路里。沒有更好的組合了。

輸入
共兩行。
第一行，兩個用空格分開的整數： C 和 B
第二行，B個用空格分開的整數，分別表示每桶中食物所含的卡路里。

輸出
共一行，一個整數，表示平平能獲得的最大卡路里，使她不違反減肥的規則。

輸入樣例
40 6
7 13 17 19 29 31

[樣例輸出]
39

三個袋子
（bags.pas/c/cpp/in/out）
時限:1 sec | 內存: 64 MB
背景
??? 平平在公園里游玩時撿到了很多小球，而且每個球都不一樣。平平找遍了全身只發現了3個一模一樣的袋子。他打算把這些小球都裝進袋子里（袋子可以為空）。他想知道他總共有多少種放法。

題目描述
??? 將N個不同的球放到3個相同的袋子里，求放球的方案總數M。
??? 結果可能很大，我們僅要求輸出M mod K的結果。
??? 現在，平平已經統計出了N<=10的所有情況。見下表：
N?1?2?3?4?5?6?7?8?9?10
M?1?2?5?14?41?122?365?1094?3281?9842

輸入
兩個整數N,K，N表示球的個數。

輸出
輸出僅包括一行，一個整數M mod K 。

輸入樣例 ( bags.in )
11 10000

輸出樣例( bags.out )
9525

數據規模
對于 40%數據,10<=N<=10,000
對于100%數據,10<=N<=1,000,000,000
對于 100%數據，K<=100,000

智捅馬蜂窩
（clever.pas/c/cpp/in/out）
時限:1 sec | 內存: 64 MB
背景
??? 為了統計小球的方案數，平平已經累壞了。于是，他摘掉了他那800度的眼鏡，躺在樹下休息。
??? 后來，平平發現樹上有一個特別不一樣的水果，又累又餓的平平打算去把它摘下來。
題目描述
??? 現在，將大樹以一個N個節點的無向圖的形式給出，每個節點用坐標（Xi，Yi）來表示表示，平平要從第一個點爬到第N個點，除了從一個節點爬向另一個相鄰的節點以外，他還有一種移動方法，就是從一個節點跳下，到達正下方的某個節點（之間可隔著若干個點和邊），即當Xj=Xi and Yi<Yj 時，平平就可以從j節點下落到i節點，他下落所用時間滿足自由落體公式，t=sqrt((Yj-Yi)*2/g) （注意：g取10）。如果出現兩線相交的情況，我們不認為它們是相通的。

輸入
兩個整數N,V，N表示節點個數，V表示平平爬樹的速度。
接下來N行，每行包含3個整數X,Y,F，X,Y是這個點的坐標，F是他的父節點（F一定小于這個點的標號，第一行的F為0）。
注意：兩節點間距離按歐幾里德距離計算 dis = sqrt( ( x1 – x2 ) 2+ ( y1 – y2 )2 )

輸出
輸出僅包括一行，從1到N所用的最少所需時間T，保留兩位小數。

輸入樣例 ( clever.in )
9 1
5 0 0
5 5 1
6 5 2
7 6 2
6 9 2
3 6 2
4 5 2
3 2 7
7 2 3

輸出樣例 ( clever.out )
8.13

數據規模
對于100%數據,1<=N<=100,1<=V<=10,0<=X,Y<=100.
建議使用extended(pas)或double（c and c++）計算，我們對于精度造成的誤差將不予重測。

過河
（river.pas/c/cpp/in/out）
時限:1 sec | 內存: 64 MB
背景
??? 經過一番努力，平平終于摘到了水果，拿近一看才發現是馬蜂窩。
??? 平平從樹上掉了下來，沒命的跑啊跑啊……
??? 后來，他發現前方有一條河。現在他用電話求助于你，希望你在他跑到之前鋪好過河的路，讓他順利過河。

題目描述
??? 已知河的長度為L，現在我們有M個石子，我們可以把一個石子鋪在河上的一個點，讓平平踩著這些石頭過河。河上已經有N個石子，而且已知平平每步跨出的距離為S到T之間的整數（ S <= T ），起點是0點，河為1到L，只要平平最后能跳過L（必須大于L）就算平平順利過河。
??? 如果平平能夠過河，請輸出最少步數，否則輸出最遠到達的距離，以便我們及時去救起平平。

輸入
第一行有五個整數L,N,M,S,T ，L是河的寬度，N表示河里原來就有N個石頭，M表示我們手上擁有的石頭，S,T表示平平的一步最小的跨度和最大跨度。接下來N行有一個值表示在河里的石頭的位置（從小到大給出）。

輸出
輸出僅包括一行，如果能夠過河，輸出最少步數，否則輸出平平能夠到達的最遠距離。

輸入樣例 ( river.in )
樣例1：
8 2 2 2 3
2
3

樣例2：
10 1 1 1 2
2

輸出樣例 ( river.out )
樣例1：
3

樣例2：
4

數據規模
對于40%數據,1<=M<=L<=1000 , 1<=S<=T<=10 ;
對于100%數據,1<=M<=L<=100000;
對于100%數據,1<=S<=T<=100,1<=N<=100.

后記
??? 可憐的平平還是沒有逃過被馬蜂蟄的命運。大老板以最快的速度把平平送到了醫院。
平平的故事就此告一段落。現在平平小朋友正躺在家里好好休息，準備沖刺2007年的NOIP……
================================================================================================================

解題報告：

第一題：
??????????? 簡單的01背包，就算使用回溯法枚舉所有可能情況也能過（經測試），數據很弱。。。。。。。
????????????本人用DP方法，求出了所有可能得到的卡路里值
????????????附上程序：

?
第二題：
????????????無奈的數學題，快速冪，或者干脆用矩陣乘法加速，看著辦吧

第三題：
????????????簡單的單元最短路，注意如果可能掉下來而不用爬的方法，更新兩點間的通路時間，其他沒什么了。
??????????? Dijkstra算法，代碼：?

第四題：
????????????讓人崩潰的DP題目，不過由于數據比較弱，搜索應該也是可以過的（不過本人不會）。

????????????首先我們應該明確題目中的幾個重要部分（或者說是細節步驟，要不然就是過河時的一般規律）：
????????????1、如果可能到達河岸對面，那么，手中的石頭全部使用完肯定對應至少一個最優解（為什么？自己想，簡單的很）；
????????????2、對于兩個石頭之間，是否存在可能到達方式的判斷條件：len/s*t>=len（len為兩石頭間的距離，下同）? (具體證明，可以形象的畫一畫）；
????????????3、如果兩個點（或者說石頭），如果之間有可能的方法到達（即滿足2中的判斷條件），那么，從一個石頭到達另一個石頭所需要踩過的其他石頭（即非這兩個石頭）的數目為 (len-1)/t,并且可以保證一定有這樣子的一種到達方法。

????????????接下來，就應該介紹動態轉移方程，以及相關的預處理了。
????????????對于數據，我們首先要進行一些必要的預處理：
????????????1、對于讀入的每個石頭的位置，通過對于上述條件的判斷，如果從0點不可到達，則可以將次石頭略去不考慮；
????????????2、因為題目要求一定要過河（就是行動的總距離要大于L才行），所以就在 L+1~L+S 這S個位置上人為的構造出S個石頭，并認為這些石頭是本身存在與河面上的。
????????????3、對于上面提到的每一個石頭，應該對其預處理出一個值（我將其保存在B數組中），代表從0點到達這個石頭中間要踩過多少個石頭（這里踩過的石頭可以是已有的，可以是從手中放下的，石頭數允許是不合法的。注意：這個數組只是表示這一種可能情況，不表示一定滿足輸入數據）；
????????????4、動態規劃的初始狀態 F[i][0]=b[i]+1。

????????????接下來，介紹動態規劃中狀態的表示方法：
????????????F[i][j]表示從0點到第i個石頭，中間如果踩過j個石頭，所需要的最少步數。（注意：此處是踩過，如果只是經過某個石頭而不必踩過，則這個石頭就不包含在這j個石頭中）。

????????????動態轉移方程：
????????????F[j][k+ifneed(i)]=min{F[i][k]+w[i][j]+1} (0<=k<i),其中w[i][j]表示從第i個石頭到第j個石頭中間要踩過的石頭數，ifneed表示一種判斷條件，就是用來判斷如果到達第j個石頭,是否一定要踩到第i個石頭上面,如果必要,則返回1,否則返回0。具體的判斷方法實現如下：


????????????最后就是對結果的判斷了。

????????????第一項，應該是判斷是否存在能夠過河的方法。由于可以明顯的看出，在上述動態規劃的過程中，由于判斷了中轉石頭是否必要踩過，已經形成了一定的貪心規則。所以，在輸出時，就應該對最后s個石頭（就是自己加進去的石頭判斷），如果b[i]滿足條件，就取其中最小的；如果b[i]>m，就取F[i][b[i]-m]里最小的。（原因應該很簡單，因為上面在轉移和預處理時已經保證了得到最優）
????????????第二項，就是在第一項沒有找到過河步數是，求出最遠走到哪里了。這里就更為簡單了：1、最近可以走m*t的距離；2、如果F[i][j]可行（就是不為0），并且滿足m+j>=b[i]，就判斷rock[i]+(m+j-b[i])*t 是否為可行解即可。
????????????
????????????再來分析一下時間復雜度，由于石頭數不大于100，s也不大于10，對于上述O(N^3)的算法是絕對不會超時的。這樣，這道題就完美解決了。

附上代碼：