状态转移方程：f_min[i][i] = 0, f_min[i][j] = min(f_min[i][k] + f_min[k+1][j] + sum[j] - sum[i-1];

---

Code:

#include 
    
     #include 
     
      #include 
      
       using namespace std;//Mystery_Sky//#define INF 0x3f3f3f3f#define M 5500int f_min[M][M];int n, sum[M];int main() {    memset(f_min, INF, sizeof(f_min));    scanf("%d", &n);    int x;    for(int i = 1; i <= n; i++) {        scanf("%d", &x);        sum[i] = sum[i-1] + x;        f_min[i][i] = 0;    }    for(int i = n; i >= 1; i--) {        for(int j = i + 1; j <= n; j++) {            for(int k = i; k <= j - 1; k++) {                f_min[i][j] = min(f_min[i][j], f_min[i][k] + f_min[k+1][j] + sum[j] - sum[i - 1]);            }        }    }    printf("%d\n", f_min[1][n]);    return 0;}