设 $dp_{i,j,0/1}$ 表示将序列缩减到 $[i,j]$，这次选择从开头还是结尾缩减的最大值。则存在转移 $dp_{i,j,0}=\max\{dp_{i-1,j,0}+a_{i-2}^{a_{i-1}},dp_{i-1,j,1}+a_{j+1}^{a_{i-1}}\}$ $dp_{i,j,1}=\max\{dp_{i,j+1,0}+a_{i-1}^{a_{j+1}},dp_{i,j+1,1}+a_{j+2}^{a_{j+1}}\}$ 则答案为 $\max\limits_{i=1}^ndp_{i,i-1,*}$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int P=998244353;
int T,n,a[1010],dp[1010][1010][2];
int qpow(int x,int y){
  if(!x&&!y) return 0;
  int res=1;
  for(;y;y>>=1,x=x*x%P)
    if(y&1) res=res*x%P;
  return res;
}
main(){cin.tie(0)->sync_with_stdio(0);int T;cin>>T;while(T--){
  for(int i=0;i<=n+1;++i)
    for(int j=0;j<=n+1;++j)
      dp[i][j][0]=dp[i][j][1]=0;
  cin>>n;
  for(int i=1;i<=n;++i) cin>>a[i];
  for(int l=2;l<=n;++l)
    for(int i=1,k=l-1;i<=l;++i,--k){
      int j=n-k-1;
      if(i-2>=0) dp[i][j][0]=dp[i-1][j][0]+qpow(a[i-2],a[i-1])%P;
      dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][1]+qpow(a[j+1],a[i-1])%P);
      dp[i][j][1]=max(dp[i][j+1][0]+qpow(a[i-1],a[j+1])%P,dp[i][j+1][1]+qpow(a[j+2],a[j+1])%P);
    }
  int ans=0;
  for(int i=1;i<=n;++i) ans=max({ans,dp[i][i-1][0],dp[i][i-1][1]});
  cout<<ans<<'\n';                   }
}

所以问题在哪里呢qwq