f[i][j][0]和f[i][j][1]分別表示從i到j,最後一個從前和從後加入的方案數,然後就可以DP了。(轉移方程詳見程序)
注意i=j和i+1=j的特殊情況。
#include#include #include #include #include #include #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define maxn 2005 #define mod 19650827 using namespace std; int n; int a[maxn],f[maxn][maxn][2]; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read(); F(i,1,n) a[i]=read(); memset(f,0,sizeof(f)); F(i,1,n) f[i][i][0]=f[i][i][1]=1; D(i,n-1,1) F(j,i+1,n) { if (i+1==j) { if (a[i]a[i]) (f[i][j][1]+=f[i][j-1][0])%=mod; if (a[j]>a[j-1]) (f[i][j][1]+=f[i][j-1][1])%=mod; } printf("%d\n",(f[1][n][0]+f[1][n][1])%mod); }