【动态规划】计蒜客：跳木桩（最长递增子序列的变体）

蒜头君面前有一排 n 个木桩，木桩的高度分别是h1,h2,h3…hn。蒜头第一步可以跳到任意一个木桩，接下来的每一步蒜头不能往回跳只能往前跳，并且跳下一个木桩的高度 不大于 当前木桩。蒜头君希望能踩到尽量多的木桩，请你帮蒜头计算，最多能踩到多少个木桩。 
输入格式 
第一行输入一个整数 n 代表木桩个数。第二行输入 n 个整数h1,h2,h3..hn，分别代表 n 个木桩的高度。(1≤n≤1000,1≤hi≤100000) 
输出格式 
输出一个整数，代表最多能踩到的木桩个数，占一行。 
样例输入 
6 
3 6 4 1 4 2 
样例输出 
4

题意：求一组数的最长非递增子序列的长度

dp[i]表示以nums[i]结尾的最长非递增子序列的长度

初始化： dp[0]=0

状态转移方程：dp[i]=max{dp[j]}+1,if(nums[j]>=nums[i]) 0<=j

代码：

#includeusing namespace std;int nums[100];int dp[100];int n;int main(){cin>>n;for(int i=0;i>nums[i];}dp[0]=nums[0]; int res=INT_MAX;for(int i=0;i=nums[i])dp[i]=max(dp[i],dp[j]+1); res=max(res,dp[i]);}}cout<