转移方程：dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+(sum[j]-sum[k])*(k-i+1)+a[i]*(k-i));
一开始思路好像出了一点问题，我是考虑每次更新时把k放到第j个位置，然后k+1到j整体前移，但是不知道错在哪里了，
正解是，对于转移方程应该是每次把i放到第k的位置，更新从k+1到j 的位置
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pii pair<int,int> #define C 0.5772156649 #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1using namespace std;const double g=10.0,eps=1e-7; const int N=500+10,maxn=60000+10,inf=0x3f3f3f;ll a[N],sum[N],dp[N][N]; int main() {ios::sync_with_stdio(false);cin.tie(0);ll t,cnt=0;cin>>t;while(t--){ll n;cin>>n;sum[0]=0;for(int i=1; i<=n; i++){cin>>a[i];sum[i]=sum[i-1]+a[i];}memset(dp,0,sizeof dp);for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)dp[i][j]=1e18;for(int len = 1 ; len <= n-1 ; len ++){for(int i=1,j=len+i;j<=n;i++,j++){for(int k=i; k<=j; k++){// cout<<k<<endl;dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+(sum[j]-sum[k])*(k-i+1)+a[i]*(k-i));// cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; }}}cout<<"Case #"<<++cnt<<": "<<dp[1][n]<<endl;}return 0; } /******************** 2 5 1 2 3 4 5 5 5 4 3 2 2 put i into the dark room dp i ... k-1 k+1 ... j k id i-1 ... k-2 k-1 ... j-2 j-1 ********************/