用区间DP做的 WA on #4。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[1010],dp[1010][1010][2];
const int md=998244353;
int pw(int x,int y){
	int s=1;
	while(y){
		if(y&1)s=s*x%md;
		x=x*x%md;
		y>>=1ll;
	}
	return s;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		if(n==2){
			printf("%lld\n",max(pw(a[1],a[2]),pw(a[2],a[1])));
			continue;
		}
		memset(dp,-0x3f3f3f3f,sizeof dp);
		dp[1][n-1][1]=dp[2][n][0]=0;
		for(int i=n-2;i>=1;i--){
			for(int l=1;l<=n-i+1;l++){
				int r=l+i-1;
				if(l>2)dp[l][r][0]=max(dp[l][r][0],dp[l-1][r][0]+pw(a[l-2],a[l-1]));
				if(l>1&&r<n)dp[l][r][0]=max(dp[l][r][0],dp[l-1][r][1]+pw(a[r+1],a[l-1]));
				if(l>1&&r<n)dp[l][r][1]=max(dp[l][r][1],dp[l][r+1][0]+pw(a[l-1],a[r+1]));
				if(r<n-1)dp[l][r][1]=max(dp[l][r][1],dp[l][r+1][1]+pw(a[r+2],a[r+1]));
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			if(i>1)ans=max(ans,dp[i][i][0]+pw(a[i-1],a[i]));
			if(i<n)ans=max(ans,dp[i][i][1]+pw(a[i+1],a[i]));
		}
		printf("%lld\n",ans);
	}
	return 0;
}