題面：

G. Snow Boots

Input ?le: standard input Output ?le: standard output Time limit: 1 second Memory limit: 256 megabytes It’s winter on the farm, and that means snow! There are N tiles on the path from the farmhouse to the barn, conveniently numbered 1...N, and tile i is covered in fi feet of snow. Farmer John starts o? on tile 1 and must reach tile N to wake up the cows. Tile 1 is sheltered by the farmhouse roof, and tile N is sheltered by the barn roof, so neither of these tiles has any snow. But to step on the other tiles, Farmer John needs to wear boots! In his foul-weather backpack, Farmer John has B pairs of boots, numbered 1...B. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair i lets FJ step in snow at most si feet deep, and lets FJ move at most di forward in each step. Unfortunately, the boots are packed in such a way that Farmer John can only access the topmost pair at any given time. So at any time, Farmer John can either put on the topmost pair of boots (discarding his old pair) or discard the topmost pair of boots (making a new pair of boots accessible). Farmer John can only change boots while standing on a tile. If that tile has f feet of snow, both the boots he takes o? AND the boots he puts on must be able to withstand at least f feet of snow. Intermediate pairs of boots which he discards without wearing do not need to satisfy this restriction. Help Farmer John minimize waste, by determining the minimum number of pairs of boots he needs to discard in order to reach the barn. You may assume that Farmer John is initially not wearing any boots. Input The ?rst line contains two space-separated integers N and B (2 ≤ N,B ≤ 250). The second line contains N space-separated integers. The ith integer is fi, giving the depth of snow on tile i (0 ≤ fi ≤ 109). It’s guaranteed that f1 = fN = 0. The next B lines contain two space-separated integers each. The ?rst integer on line i + 2 is si, the maximum depth of snow in which pair i can step. The second integer on line i + 2 is di, the maximum step size for pair i. It’s guaranteed that 0 ≤ si ≤ 109 and 1 ≤ di ≤ N ?1. The boots are described in top-to-bottom order, so pair 1 is the topmost pair in FJ’s backpack, and so forth. Output The output should consist of a single integer, giving the minimum number of boots Farmer John needs to discard. It’s guaranteed that it will be possible for FJ to make it to the barn. Example Input 10 4 0 2 8 3 6 7 5 1 4 0 2 3 4 2 3 4 7 1 Output 2

題目描述：

農夫想從農舍到谷倉（去喂奶牛？），去谷倉的路由N個瓷磚組成，按1-N編號，農夫從瓷磚1出發到瓷磚N，就可以到達谷倉了。由于下雪，瓷磚被雪不同程度地覆蓋（有的瓷磚上積雪厚一點，有的薄一點）。因此，農夫必須穿靴子才能走到谷倉。在農夫的背包里，有B雙靴子，按1-B編號。這些靴子有高的，也有矮的；有的跨一步跨遠一點的（假如一雙最多能跨x距離，那么，農夫可以穿著這雙鞋子跨1距離，2距離...x距離），有的跨一步跨近一點。但是這個背包有個特點：只能拿背包最上面的靴子（這是什么背包來的，只能拿最上面的靴子? →_→），如果要拿背包下面的靴子，就只能把背包最上面的靴子丟掉，直到想拿到的靴子“浮”現在背包的最上面（有點像棧，可以用棧理解這個背包）。當前站的位置穿的鞋子高度不能低于積雪高度（低于的話靴子會“進”雪 ( ⊙ o ⊙ ) ）。如果想要換一雙靴子，就必須從背包拿出比當前積雪要高的靴子，然后穿上新鞋子，丟掉舊鞋子。求：怎樣走才能使丟棄的鞋子數量最小，輸出丟棄鞋子最小的數量

題目分析：

前言：這道題我看英文的時候各種看不懂，樣例都看不懂（太渣了? ( /。\ )? ），到后面又忽略了一些細節，導致想了很久（?(T_T)?） 這道題是用動態規劃去解決的，我們可以先看看樣例是怎樣的（看懂樣例的可以無視我這渣渣解說）： 首先，我們是在瓷磚1的位置，也就是： 由題意得知，我們在第1塊瓷磚上是沒有穿靴子的，這時我們穿上靴子1，背包情況： 然后往前面跨三塊瓷磚，到達瓷磚4，也就是： 這時我們發現，這個靴子無論是跨幾步瓷磚，都不能往前走了，所以我們要拿出新靴子，看能不能繼續往前走。 這時我們丟棄了靴子1，穿上了靴子2，發現最多只能跨兩個瓷磚，也就是最遠距離到： 但是還是不行，因為和靴子1的問題一樣，無論到哪個瓷磚靴子都會進“雪”（靴子高度不夠） 所以，我們要再換一雙鞋子，然后丟掉舊鞋子： 之后，我們就可以這樣走： 這樣農夫就穿著靴子3成功到達了終點，路上丟棄了兩雙鞋子 當然，剛開始的時候我們在出發時就從背包拿出靴子3（首先要丟棄靴子1和靴子2），然后直接穿著這個靴子到達終點。 也是只需要丟棄兩雙鞋子。 那這道題怎樣用動態規劃呢？一般動態規劃的題有這樣的特點：有多種途徑求出到“最”值，而且當前第n個狀態的最值可以由前n-1個狀態的最值推算出來。特點1已經符合了，那么，我們可能會往動態規劃方面去想：這個題目的問題：到達第N個瓷磚所需要丟棄的最少鞋子。子問題：到達第i個瓷磚所需要丟棄的最少鞋子（1 <= i < N）。這時需要考慮：假設知道了子問題的結果，怎樣計算要求的問題。在這里就是：如果我到達了第i個瓷磚，怎樣選才能到達第N個瓷磚？（我的代碼是按照這個想法寫的，想法不同代碼也不同，動態規劃的題AC代碼不唯一）。在這里我是從前面去“更新”后面的值（即由前面瓷磚的最少丟棄鞋子“更新”到后面瓷磚的最少丟棄鞋子），dp[i]定義為到當前第i個瓷磚要丟棄的最少鞋子。這個dp[i]有個特點：由dp[i]還可以推測到第i個瓷磚時農夫正在穿的鞋子，為什么？因為背包比較特殊，取出來和穿過的鞋子不能再放回背包，所以農夫到第i個瓷磚穿的鞋子就是dp[i]+1，可以用上面解釋樣例的背包圖理解一下這個。 解決完這些問題，基本上可以寫出代碼出來了，不過有一點要注意的是：從當前瓷磚到下一個瓷磚，如果要換鞋子的話，拿出鞋子的高度就不能低于當前瓷磚的雪的高度；如果要到下一個瓷磚，那么穿的鞋子一定不能低于下一個瓷磚的高度。有點人可能對dp數組的初始化有疑問：如果按照上面dp數組的解說，dp[1] = 0，即第1個瓷磚正在穿的鞋子是dp[1]+1 = 1，也就是第1雙鞋子，但是題目說在第1個瓷磚沒有穿鞋子啊。其實這個自己仔細考慮一下，第1個瓷磚穿與不穿第1雙鞋子是不是沒有影響？為了更方便我們計算，就假設在第1個瓷磚穿著第1雙鞋子，也就是dp[1] = 0. AC代碼： 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 #include <set> 6 #include <algorithm> 7 using namespace std; 8 const int inf = 0x3f3f3f3f; 9 int n, b; 10 int f[255], s[255], d[255]; 11 int dp[555]; 12 13 void test(){ 14 cout <<endl; 15 for(int i = 1 ; i <= n ; i++){ 16 printf("dp[%d] : %d\n", i, dp[i]); 17 } 18 } 19 20 int main(){ 21 cin >> n >> b; 22 for(int i = 1; i <= n; i++){ 23 cin >> f[i]; 24 } 25 for(int i = 1; i <= b; i++){ 26 cin >> s[i] >> d[i]; 27 } 28 29 memset(dp, inf, sizeof(dp)); 30 dp[1] = 0; //第1個瓷磚丟棄0雙鞋子，可以表示當前正在穿第1雙鞋子 31 32 33 for(int i = 1; i <= n; i++){ 34 int u = dp[i]+1; //第i個瓷磚丟器正在穿第u雙鞋子 35 for(int j = u; j <= b; j++){ //穿第j雙鞋子到下一個瓷磚 36 for(int k = 1; k <= d[j]; k++){ //到第i+k個瓷磚 37 if(f[i+k] <= s[j] && f[i] <= s[j]){ //穿的鞋子高于等于當前瓷磚和下一個瓷磚 38 dp[i+k] = min(dp[i+k], j-1); //穿第j雙鞋子到第i+k個瓷磚，丟棄了j-1雙鞋子 39 //min()是更新操作，也就是如果其他瓷磚到達第i+k個瓷磚有更小的丟棄數量就更新為更小的 40 } 41 } 42 } 43 } 44 45 //test(); 46 47 cout << dp[n] << endl; 48 49 return 0; 50 }

?

?

轉載于:https://www.cnblogs.com/happy-MEdge/p/10405028.html

總結

以上是生活随笔為你收集整理的2019 GDUT Rating Contest II : Problem G. Snow Boots的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。