n<=1000 O(n^3) 80pts

#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=998244353;
int a[N],n;
int f[N][N],g[N][N];
int c[1010][1010];
int st[1010][10];
int lg[1010];
inline void init(){
	lg[0]=-1;
	for(int i=1;i<=n;i++)	lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++)	st[i][0]=a[i];
	for(int i=1;(1<<i)<=n;i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		}
	}
}
inline int query(int l,int r){
	return max(st[l][lg[r-l+1]],st[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
inline void dfs(int l,int r){
	if(f[l][r]!=0x3f3f3f3f)	return;
	if(l==r){
		f[l][r]=0;g[l][r]=1;return;
	}
	int v=query(l,r);
	if(a[l]==v&&l<r){
		dfs(l+1,r);
		int v=f[l+1][r]+query(l+1,r);
		if(v<f[l][r])	f[l][r]=v,g[l][r]=g[l+1][r];
		else{
			if(v==f[l][r]){
				g[l][r]=(g[l][r]+g[l+1][r])%998244353;
			}
		}
	}
	if(a[r]==v&&l<r){
		dfs(l,r-1);
		int v=f[l][r-1]+query(l,r-1);
		if(v<f[l][r])	f[l][r]=v,g[l][r]=g[l][r-1];
		else{
			if(v==f[l][r]){
				g[l][r]=(g[l][r]+g[l][r-1])%998244353;
			}
		}
	}
	for(int k=l+1;k<r;k++){
		if(a[k]!=v)	continue;
		dfs(l,k-1);dfs(k+1,r);
		int v=f[l][k-1]+f[k+1][r]+query(l,k-1)+query(k+1,r);
		if(v<f[l][r])	f[l][r]=v,g[l][r]=1ll*g[l][k-1]*g[k+1][r]%998244353*c[r-l][k-l]%998244353;
		else{
			if(v==f[l][r]){
				g[l][r]=(g[l][r]+1ll*g[l][k-1]*g[k+1][r]%998244353*c[r-l][k-l]%998244353)%998244353;
			}
		}
	}
	return;
}
int main(){
	c[0][0]=1;
	for(int i=1;i<=1005;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
		}
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	init();
	memset(f,0x3f,sizeof f);
	dfs(1,n);
	printf("%d\n",g[1][n]);
	return 0;
}

70pts

#include<bits/stdc++.h>
using namespace std;
const int N=1006,mod=998244353;
int a[N],n;
int f[N][N],g[N][N];
int c[1006][1006];
int st[1006][10];
int lg[1006];
void init(){
	lg[0]=-1;
	for(int i=1;i<=1005;i++)	lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++)	st[i][0]=a[i];
	for(int i=1;i<10;i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		}
	}
}
inline int query(int l,int r){
	if(l>r)	return 0;
	int v=lg[r-l+1];
	return max(st[l][v],st[r-(1<<v)+1][v]);
}
int main(){
	c[0][0]=1;
	for(int i=1;i<=1005;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%998244353;
		}
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	init();
	memset(f,0x3f,sizeof f);
	for(int i=1;i<=n+1;i++){
		f[i][i]=0;g[i][i]=1;
		f[i][i-1]=0;g[i][i-1]=1;
	}
	for(int len=2;len<=n;len++){
		for(int l=1,r=len;r<=n;l++,r++){
			int v=query(l,r);
			for(int k=l;k<=r;k++){
				if(a[k]!=v)	continue;
				int s=f[l][k-1]+f[k+1][r]+query(l,k-1)+query(k+1,r);
				if(s<f[l][r])	f[l][r]=s;
			}
			for(int k=l;k<=r;k++){
				if(a[k]!=v)	continue;
				int s=f[l][k-1]+f[k+1][r]+query(l,k-1)+query(k+1,r);
				if(s==f[l][r]){
					g[l][r]=(g[l][r]+(long long)g[l][k-1]*g[k+1][r]%998244353*c[r-l][k-l]%998244353)%998244353;
				}
			}
		}
	}
	printf("%d\n",g[1][n]);
	return 0;
}

为什么递归比不递归更快？ 怎么优化取模的部分?