rt，求问时间复杂度。

不理解为什么过了 $50$ pts，但感觉还是 $n^3$ 。

#include <bits/stdc++.h>
using namespace std;
const long long MX=7200,INF=0x3f3f3f3f3f3f3f3f;
long long dp[MX][MX];
long long input[MX];
void solve(){
    long long n;scanf("%lld",&n);
    for(long long i=1;i<=n;i++)for(long long j=1;j<=n;j++)  dp[i][j]=INF;
    for(long long i=1;i<=n;i++)  scanf("%lld",&input[i]),dp[i][i+1]=input[i],dp[i][i]=0;
    for(long long len=3;len<=n;len++){
        long long pos=1;
        for(long long l=1;l+len-1<=n;l++){
            long long r=l+len-1;
            for(long long k=pos;k<r;k++){
                if(max(dp[l][k],dp[k+1][r])+input[k]<dp[l][r]){
                    pos=k;
                    dp[l][r]=max(dp[l][k],dp[k+1][r])+input[k];
                }
            }
        }
    }
    printf("%lld\n",dp[1][n]);
    return ;
}
signed main(){
    long long T;scanf("%lld",&T);
    while(T--){
        solve();
    }
    return 0;
}