题面

解析

\(O(n^2)\)秒出：

设\(f[0][i]\)表示保留第\(i\)个盆，并且它高于左边和右边的方案数。

设\(f[1][i]\)表示保留第\(i\)个盆，并且它低于左边和右边的方案数。

int main(){  n=gi();  fp(i,1,n) a[i]=gi();  fp(i,1,n) f[0][i]=f[1][i]=1;  fp(i,2,n)    fp(j,1,i-1)    {      if(a[i]>a[j]) f[0][i]=max(f[0][i],f[1][j]+1),ans=max(ans,f[0][i]);      if(a[i]

然后思考怎么把这个优化成\(O(n)\)。

考虑维护\(\max\{f[1][j]+1\}\)和\(\max\{f[0][j]+1\}\)

这个东西吗，其实可以从前面继承过来。

因为，即使实际上\(f[0][i]==1\)而\(f[0][i-1]==3\)，把\(f[0][i]=3\)不会影响到后面\(DP\)的结果，也不会影响到最终的答案。

但是这样\(DP\)，取前面的最大值就方便多了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define re register#define il inline#define db double#define fp(i,a,b) for(re int i=a;i<=b;++i)#define fq(i,a,b) for(re int i=a;i>=b;--i)using namespace std;const int N=1e5+100;int n,a[N],f[2][N];il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}il int max(re int x,re int y){return x>y?x:y;}int main(){ n=gi(); fp(i,1,n) a[i]=gi(); f[0][1]=f[1][1]=1; fp(i,2,n) { if(a[i]>a[i-1]) f[0][i]=max(f[0][i],f[1][i-1]+1); else f[0][i]=max(f[0][i],f[0][i-1]); if(a[i]