game turbo 4.0，Evolution Game DP

題目描述
In the fantasy world of ICPC there are magical beasts. As they grow, these beasts can change form, and every time they do they become more powerful. A beast cannot change form completely arbitrarily though. In each form a beast has n eyes and k horns, and these affect the changes it can make.

A beast can only change to a form with more horns than it currently has.
A beast can only change to a form that has a difference of at most w eyes. So, if the beast currently has n eyes it can change to a form with eyes in range [n - w, n + w].

A beast has one form for every number of eyes between 1 and N, and these forms will also have an associated number of horns. A beast can be born in any form. The question is, how powerful can one of these beasts become? In other words, how many times can a beast change form before it runs out of possibilities?

輸入
The first line contains two integers, N and w, that indicate, respectively, the maximum eye number, and the maximum eye difference allowed in a change (1 ≤ N ≤ 5000; 0 ≤ w ≤ N).
The next line contains N integers which represent the number of horns in each form. I.e. the ith number, h(i), is the number of horns the form with i eyes has (1 ≤ h(i) ≤ 1 000 000).

game turbo 4.0？輸出
For each test case, display one line containing the maximum possible number of changes.

樣例輸入
復制樣例數據
5 5
5 3 2 1 4
樣例輸出
4

提示
Start with 1 horn and 4 eyes, and it can change 4 times: (1 horn 4 eyes) -> (2 horns 3 eyes) -> (3 horns 2 eyes) -> (4 horns 5 eyes) -> (5 horns 1 eye).

首先題目意思就不是很好讀懂，先給出下面狀態的數目和眼睛與角的最大差值，之后給出的數是各個狀態下角的個數，同時這個狀態的下標也是當前狀態眼睛的個數，這只怪獸的變化過程中，角的數目必須是一直增加的，而眼睛數目必須在差值范圍內，問這只怪獸最大的形態數目是多少。

一開始以為是單純的暴力，但是哪個是第一個狀態是不確定的，這里隱含狀態的轉移，先選出里面最大的值，讓其作為末尾狀態，之后倒著遍歷，找出所有角的長度小于最大狀態且眼睛數目在范圍內的狀態，更新其狀態，之后繼續循環這個過程，直到每個狀態都以最后狀態出現過一次。選取所有情況里面的最大值即可。

GAME TURBO。AC代碼

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int maxn=5005,inf=1e9;
int dp[5005],h[5005];
int main()
{int n,w,tar=0,ans=0;scanf("%d%d",&n,&w);for(int i=1;i<=n;i++){scanf("%d",&h[i]);if(h[i]>h[tar])tar=i;}int m=n;while(m--){for(int i=1;i<=n;i++)if(h[i]<h[tar]&&abs(i-tar)<=w){dp[i]=max(dp[i],dp[tar]+1);ans=max(ans,dp[i]);}h[tar]=inf;tar=0;for(int i=1;i<=n;i++)if(h[i]!=inf&&h[i]>h[tar])tar=i;}printf("%d\n",ans);
}