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).
输出
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).
ps:dp,从后往前遍历，更新每个状态，寻找最大值
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9,N=5555;
int a[N];
int dp[N];
int main()
{
int n,w,x=0;
int ans=0;
cin>>n>>w;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>a[x]) x=i;
}
int m=n;
while(m--){
for(int i=1;i<=n;i++){
if(a[i]<a[x]&&abs(i-x)<=w){
dp[i]=max(dp[i],dp[x]+1);
ans=max(ans,dp[i]);
}
}
a[x]=inf;
x=0;
for(int i=1;i<=n;i++){
if(a[i]!=inf&&a[i]>a[x]) x=i;
}
}
cout<<ans<<endl;
return 0;
}