鏈接

題目描述

惡魔獵手尤迪安野心勃勃，他背叛了暗夜精靈，率領深藏在海底的娜迦族企圖叛變。守望者在與尤迪安的交鋒中遭遇了圍殺，被困在一個荒蕪的大島上。為了殺死守望者，尤迪安開始對這個荒島施咒，這座島很快就會沉下去。到那時，島上的所有人都會遇難。守望者的跑步速度為17m/s，以這樣的速度是無法逃離荒島的。慶幸的是守望者擁有閃爍法術，可在1s內移動60m，不過每次使用閃爍法術都會消耗魔法值10點。守望者的魔法值恢復的速度為4點/s，只有處在原地休息狀態時才能恢復。

現在已知守望者的魔法初值M，他所在的初始位置與島的出口之間的距離S，島沉沒的時間T。你的任務是寫一個程序幫助守望者計算如何在最短的時間內逃離荒島，若不能逃出，則輸出守望者在剩下的時間內能走的最遠距離。注意：守望者跑步、閃爍或休息活動均以秒(s)為單位，且每次活動的持續時間為整數秒。距離的單位為米(m)。

輸入輸出格式

輸入格式：

共一行，包括空格隔開的三個非負整數M,S,T。

輸出格式：

共兩行。

第1行為字符串“Yes”或“No”（區分大小寫），即守望者是否能逃離荒島。

第2行包含一個整數。第一行為“Yes”（區分大小寫）時表示守望者逃離荒島的最短時間；第一行為“No”（區分大小寫）時表示守望者能走的最遠距離。

輸入輸出樣例

輸入樣例#1： 39 200 4 輸出樣例#1： No 197 輸入樣例#2： 36 255 10 輸出樣例#2： Yes 6

說明

30%的數據滿足：1≤T≤10,1≤S≤100

50%的數據滿足：1≤T<≤1000,1≤S≤100001

100%的數據滿足：1≤T≤300000,0≤M≤1000,1≤S≤10的8次方

?

機房dalao：一看就是弱智dp題。然后他切了。但是我因為太菜第一想法是全都進行閃現。下面進行分析。

每次恢復魔力值10點需要2.5s，再用1s進行60m的閃現，60/3.5大概是17.14m/s的速度，剛出發的時候還有一些魔力值。跑步速度是17m/s，這樣看來似乎閃現是最優選，我們愉快的貪心吧！！于是我立馬寫了個代碼交上：

?

1 #include <iostream> 2 using namespace std; 3 int m,s,t,su; 4 int main() 5 { 6 cin>>m>>s>>t; 7 for(int i=1;i<=t;i++) 8 { 9 if(m>=10) 10 { 11 m-=10; 12 su+=60; 13 } 14 else 15 m+=4; 16 if(su>=s) 17 { 18 cout<<"Yes"<<endl<<i; 19 return 0; 20 } 21 } 22 cout<<"No"<<endl<<su; 23 return 0; 24 } 果斷就會白給 很好，樣例都沒過。但是我怎么可能這么輕易認輸呢，我干脆點了提交。

雖然WA了一半，但A了一半說明它并不是全無道理。或許可以推出正確的思路呢？

以樣例為例，39 200 4這組數據正確的最遠距離結果是197，這份代碼輸出的結果則是180.我們可以看出來，最后一秒中本可以跑步17m，這份代碼卻會讓守望者原地等待。

再看36 255 10這組，正確的最短時間是6s，這份程序的結果是9s。我們人工模擬一下，可以發現在5s-6s時我們可以選擇跑步啊！而這個廢物代碼卻會原地等待3s后再進行閃現。

這時我又覺得我會了！只要判斷一下不就好了嗎！

1 #include <iostream> 2 using namespace std; 3 int m,s,t,su; 4 int main() 5 { 6 cin>>m>>s>>t; 7 for(int i=1;i<=t;i++) 8 { 9 if(s-su<=17) 10 { 11 cout<<"Yes"<<endl<<i; 12 return 0; 13 } 14 if(i==t&&m<10) 15 { 16 cout<<"No"<<endl<<su+17; 17 return 0; 18 } 19 if(m>=10) 20 { 21 m-=10; 22 su+=60; 23 } 24 else 25 m+=4; 26 if(su>=s) 27 { 28 cout<<"Yes"<<endl<<i; 29 return 0; 30 } 31 } 32 cout<<"No"<<endl<<su; 33 return 0; 34 } 猶豫就會敗北

好，這次看起來好多了，我們再提交一下試試。

只是多A了一個點，說明優化還是有問題。思考過后我們可以想到，每秒中我們有三種決定：閃現、跑步和停留。停留和閃現可以合并在一起，我們的優化只給了最后一秒跑步的選擇。

于是我們可以運用一種似乎很像動態規劃的解法啦！我們先假設全部進行閃現-停留-閃現操作，再加一個循環判斷每秒的最優決策究竟是閃現-停留還是跑步。我們用dp[i]數組表示第i秒時守望者所能到的最遠距離。

1 #include <iostream> 2 using namespace std; 3 long long m,s,t,dp[300001];//dp[i]數組表示第i秒時守望者所能到的最遠距離 4 int main() 5 { 6 cin>>m>>s>>t; 7 for(int i=1;i<=t;i++)//相當于第一次提交的程序 8 if(m>=10) 9 { 10 m-=10; 11 dp[i]=dp[i-1]+60; 12 } 13 else 14 { 15 m+=4; 16 dp[i]=dp[i-1]; 17 } 18 for(int i=1;i<=t;i++) 19 { 20 dp[i]=max(dp[i],dp[i-1]+17);//如果在第i秒時跑步能到達更遠距離，我們跑步 21 if(dp[i]>=s)//已到達就可以輸出+結束程序啦 22 { 23 cout<<"Yes"<<endl<<i; 24 return 0; 25 } 26 } 27 cout<<"No"<<endl<<dp[t];//如果進行到了這里說明無法逃離，我們輸出能到達的最遠距離 28 return 0; 29 } 人生不如意十有八九

?

這次的樣例也過了，于是我們提交一下。

?

一道黃題耗我十五分鐘我果然還是太菜了

這樣就通過了！如果有興趣的話大家可以研究一下暴力寫法，也是能過的（我懶得想了

謹記教訓：猶豫就會敗北，果斷就會白給！！！

轉載于:https://www.cnblogs.com/BatmanWhoLaughs/p/10873997.html

總結

以上是生活随笔為你收集整理的洛谷P1095守望者的逃离题解-伪动态规划/贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

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