嘻嘻，這是一道典型的DP題目，但貌似網上都沒有類似的題解，那兔子就來說一說吧！

黑熊過河

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

思路

入手點：
反正就是老一套的動態轉移公式和老生常談的邊界問題。
動態轉移公式：
我們可以從題目中得到，黑熊可以從a[i-1]與a[i-2]兩個方向來，而a[i-1]和a[i-2]又可以從它們的-1或-2個獲得。（如圖）

so，所以你想到什么沒有？
dp[i]=max(dp[i-1],dp[i-2])-q+a[i];
就是它！

_{嘻嘻嗎，皮了一波，轉移到正題上面}

基本框架：

#include<bits/stdc++.h> using namespace std; 建立 需要的數據結構； int main(){cin部分；for(i:所在河岸下標-對應河岸下標){if(要求上次或上上次>0){變DP[i]的值}if(dp[i]沒有體力值了){dp[i]=極小值}}if(不能到對岸){cout<<"NO";return 0;}cout<<dp[n+1];return 0; }

AC代碼

#include<bits/stdc++.h> using namespace std; int p,q,n,a[1000100],dp[1000010];int main(){cin>>p>>q>>n;for(int i=1;i<=n;i++){cin>>a[i];}//cin沒什么好講的dp[0]=p;//下標0是所在河岸，n+1是對岸dp[1]=p-q>=0 ? p-q+a[1] : -0x7f7f7f7f ;//我們對dp[0]、dp[1]預處理for(int i=2;i<=n+1;i++){//0,1下標已經處理，所以從2開始bool flag=0;//判斷是否dp[i]的獲得點為熊跳不過，若沒有改變初值則兩點都跳不到dp[i]if(dp[i-1]-q>=0){//從dp[i-1]到達flag=1;dp[i] =max(dp[i], dp[i-1]-q+a[i]);}if(dp[i-2]-q>=0){//從dp[i-2]到達flag=1;dp[i]=max(dp[i], dp[i-2]-q+a[i]);}if(!flag){//跳不到dp[i]dp[i]=-0x7f7f7f7f;}}if(dp[n+1]<0){cout<<"NO";return 0;}cout<<dp[n+1];return 0; }

本期題解就到這里，希望小伙伴們點個關注，下期我們再會，233333333~拜啦！！

總結

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

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