//動態規劃-基礎

題目描述

晶晶的爸爸給晶晶出了一道難題：有一只黑熊想過河，但河很寬，黑熊不會游泳，只能借助河面上的石墩跳過去。它可以一次跳一墩，也可以一次跳兩墩，但是每跳一次都會耗費一定的能量，黑熊最終可能因能量不夠而掉入水中。所幸的是，有些石墩上放了一些食物，些食物可以給黑熊增加一定的能量。問黑熊能否利用這些石墩安全地抵達對岸？請計算出抵達對岸后剩余能量的最大值。

輸入輸出格式

輸入格式：

第1行包含兩個整數P和Q（0≤P,Q≤1000），其中P表示黑熊的初始能量，Q表示黑熊每次起跳時耗費的能量。

第2行只有一個整數n（1≤n≤10^6），表示河中石墩的數目。

第3行有n個整數，表示每個石墩上食物的能量值ai（0≤ai≤1000）。

輸出格式：

輸出1行，若黑熊能抵達對岸，輸出抵達對岸后剩余能量的最大值；若不能，則輸出“NO”。

輸入輸出樣例

輸入樣例#1：

12 5 5 0 5 2 0 7

輸出樣例#1：

6

$AC$代碼：

#include<bits/stdc++.h> using namespace std; int n,q,p,sub,a[1000005],f[1000005]; int main() {cin>>p>>q>>n;//其中P表示黑熊的初始能量，Q表示黑熊每次起跳時耗費的能量。for(int i=1;i<=n;i++)cin>>a[i];f[0]=p;//初始能量for(int i=1;i<=n+1;i++){sub=max(f[i-1],f[i-2]);//前兩個，注:每次最多跳2格 if(sub>=q) f[i]=sub-q+a[i];//剩余能量 else//if(sub<q) {cout<<"NO"<<endl; //因能量不夠而掉入水中return 0;//結束程序 }}cout<<f[n+1]<<endl; //最后能量 return 0; }

總結

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

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