目錄
題目
題解
題目
- 1000ms
- 32768K
有一個小球掉落在一串連續的彈簧板上，小球落到某一個彈簧板后，會被彈到某一個地點，直到小球被彈到彈簧板以外的地方，
假設有 n 個連續的彈簧板，每個彈簧板占一個單位距離，a[i] 代表代表第 i 個彈簧板會把小球向前彈 a[i] 個距離，比如位置 1 的彈簧能讓小球前進 2 個距離到達位置 3，如果小球落到某個彈簧板后，經過一系列彈跳會被彈出彈簧板，那么小球就能從這個彈簧板彈出來，現在希望你計算出小球從任意一個彈簧板落下，最多會被彈多少次后，才會彈出彈簧板，
輸入格式
第一個行輸入一個 n 代表一共有 n(1≤n≤100000) 個彈簧板，第二行輸入 n 個數字，中間用空格分開，第 i 個數字 ai?(1≤ai?≤30) 代表第 i 個彈簧板可以讓小球移動的距離，
輸出格式
輸出一個整數，代表小球最多經過多少次才能彈出彈簧板，
輸出時每行末尾的多余空格，不影響答案正確性
要求使用「檔案輸入輸出」的方式解題，輸入檔案為 spring.in，輸出檔案為 spring.out
樣例輸入
5
2 2 3 1 2
樣例輸出
3
題解：
知識點：DP
分析：我們首先用dp[i]來記錄第i位置跳出邊界的次數，然后得出dp狀態轉移方程：dp[i]=dp[i+a[i]]+1，第i位置跳出邊界的次數=他能跳到的位置跳出邊界的次數+1，注意這里要逆序處理，
代碼：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int NOIP=1e5+35;
int a[NOIP];
int dp[NOIP];//記錄每個位置跳出邊界的次數
int main(){
freopen("spring.in","r",stdin);
freopen("spring.out","w",stdout);
int n,ans=-0x3f3f3f3f;//ans初始為負無窮
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
}
for (int i=n;i>=0;i--){//逆序處理，讀者可自行想想why(易想到，手動模擬)
dp[i]=dp[i+a[i]]+1;
ans=max(dp[i],ans);
}
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/260072.html
標籤：其他