嗯。。。。果然还是那句话，直接上组合数学搞不定的组合数学，要么打表要么dp递推。
设dp[i][j][flag]表示前i数字，令最后一个数字为j时的方法数，其中flag==0表示第i-1个比第i个小，flag==1表示第i-1大于等于第i个，然后根据题目要求就是不能出现局部极大值，所以可以写出来递推式：① dp[i][j][0]=Σ(dp[i-1][k][0]+dp[i-1][k][1]) ,1<=k<j ② dp[i][j][1]=dp[i-1][j][0]+Σdp[i-1][k][1],j<=k<=200 边界条件的话是单独考虑i==1的时候，特判算一下就可以了。这个方法是n*200个状态，每次转移再*200就是40000*n，太慢，观察到是求前缀/后缀和的形式，可以每一轮算完i之后维护一个presum[j][flag]，保存这一轮的前缀和，这样的话可以O(1)转移，复杂度就变成了n*200 。
主要的思考的点就在于在满足题目条件的约束下递推，加了一维状态表示之后问题就变得很简单了，所以推不出来的时候可以考虑加维（增加dp的信息量）
由于偷懒到处取模所以代码很慢吧。。。不过dp重要的是思想hhh
继续阅读“[CF][DP][递推关系] codeforces 1068D Array Without Local Maximums”