Description有一只黑熊想過河，但河很寬，黑熊不會游泳，只能借助河面上的石墩跳過去，他可以一次跳一墩，也可以一次跳兩墩，但是每起跳一次都會耗費一定的能量，黑熊最終可能因能量不夠而掉入水中，所幸的事，有些石墩上放了一些食物，這些食物可以給黑熊增加一定的能量，問黑熊能否利用這些石墩安全的抵達對岸，若能，則計算出抵達對岸后剩余能量的最大值是多少？Input第一行包含兩個整數P（黑熊的初始能量），Q（黑熊每次起跳時耗費的能量），（0≤P,Q≤1000）；第二行只有一個整數N（1≤N≤10^610 6），即河中石墩的數目；第三行有N個整數，即每個石墩上食物的能量值ai（0≤ai≤1000）。Output輸出文件包括一行，若黑熊能抵達對岸，輸出抵達對岸后剩余能量的最大值是多少，若不能抵達對岸，則輸出“NO”。Sample Input 1 12 5 5 0 5 2 0 7 Sample Output 16

明眼人們一眼就可以看出這道題是一道DP，可如果只能走1步，那么這道題會簡單許多，但為了攔住OIer們，他偏偏可以走1步或兩步。

算了算了，含著淚也要寫這道題。
那現在該怎么辦呢？
那我們先來畫個圖理解一下吧。

這樣看起來，這題感覺也不是很難，但要注意的是，中途熊的能量是可能小于0的，所以那是后就要給dp[i][j]賦一個極小值，不然中途又吃活了怎么辦？

源代碼（附贈注釋）：

#include <bits/stdc++.h> using namespace std; int dp[10010],a[10010]; int main(){int p,q;cin>>p>>q;int n;cin>>n;for (int i=1;i<=n;i++){cin >>dp[i];}//輸入 dp[0]=p;dp[1]+=dp[0]-q;if (dp[1]<=0){cout<<"NO";return 0;}//如果開頭都跳不過去，就直接return。 for (int i=2;i<=n+1;i++){bool sb=0;//一個普通的變量 if(dp[i-1]-q>=0){sb=1;}if(dp[i-2]-q>=0){sb=1;}if (sb){dp[i]+=max(dp[i-1],dp[i-2]-q);if (dp[i]<=0){dp[i]=-1e9;}//如果它掉到水里去了，就賦一個極小值，不能讓他吃詐尸了。 }else{dp[i]=-1e9;//走一步和走兩步都會掉到水里，那就不玩了唄 }}dp[n]-=q;if (dp[n+1]<=0){cout<<"No";}else{cout<<dp[n];}//判斷一下，可憐的熊是否還活著 return 0; }

標準結局：

總結

以上是生活随笔為你收集整理的YCOJ黑熊过河的全部內容，希望文章能夠幫你解決所遇到的問題。

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