スプリングプレート(補強)-計ニンニク客

目次
タイトル
問題解
タイトル

 1000ms

 32768K

 
小さなボールが連続したスプリングボードに落ち、小さなボールがスプリングボードの外に落ちるまで、ある場所に弾かれます.
n個の連続したスプリングプレートがあると仮定すると、各スプリングプレートは単位距離を占め、a[i]はi番目のスプリングプレートを代表して小球をa[i]個の距離まで前に弾く.例えば位置1のスプリングは、小球を2距離前進させて位置3に到達させることができる.ボールがスプリングボードに落ちた後、一連のジャンプを経てスプリングボードにポップアップされると、ボールはこのスプリングボードから弾き出すことができます.小さなボールが任意のスプリングボードから落ちて、最大何回弾かれてからスプリングボードがポップアップされるかを計算してほしい.
入力フォーマット
第1行入力nは、n(1≦n≦100000)個のスプリングプレートを表す.2行目に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
#include
#include
#include
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<