算法1
(暴力枚举) $O(n^2)$
设为困难不过分吧……
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int h[1000];
int dp[1000][1000][2];
int main()
{
int n,i,j;
cin>>n;
for(i=0;i<n;i++)cin>>h[i];
for(i=n-1;i>=0;i--)
for(j=i;j<n;j++){
if(i==j){
dp[i][j][0]=1;
continue;
}
if(h[j]>h[j-1])dp[i][j][1]+=dp[i][j-1][1];
if(h[j]>h[i])dp[i][j][1]+=dp[i][j-1][0];
if(h[i]<h[j])dp[i][j][0]+=dp[i+1][j][1];
if(h[i]<h[i+1])dp[i][j][0]+=dp[i+1][j][0];
dp[i][j][0]%=19650827;
dp[i][j][1]%=19650827;
}
cout<<(dp[0][n-1][0]+dp[0][n-1][1])%19650827;
}