2020“远光杯”网络资格赛O 军训值日生（区间dp）

区间dp）"/>

2020“远光杯”网络资格赛O 军训值日生（区间dp）

题目
每次军训课一结束，同学们都顾不得整理自己的小板凳等训练所需物品，以最快的速度冲向食堂，军训时体能消耗太大了，他们必须轻装前进，抢到自己喜欢的食物。作为军训值日生，小明的工作量非常大，他们要将自己班级中每个同学的小板凳整理好放在一起。

假设在整理前，班级中某些同学的小板凳是放在一起的，我们称放在一起的小板凳为一组小板凳，并且班级中所有小板凳是排成一排的。小明在整理自己班级小板凳的时候，会将相邻的两组小板凳整理到一起，组成一组新的板凳，所消耗的能量是两组板凳数量的乘积。

根据所给出的板凳数量及分组情况，请你帮组小明计算出整理完全班所有小板凳所消耗的最少能量。

输入要求
有多组数据（不超过5组）。
每组数据包含2行。
第一行包含一个整数n（0<n<=100），表示共有n组小板凳。
第二行包含n个整数mi（0<mi<=100），分别代表整理前每组小板凳的数量。

输出要求
每组数据输出小明整理完全班所有小板凳所消耗的最少能量。

样例输出

2
1 2
3
5 1 2

样例输出

2
17

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 110;int a[maxn],n;
ll dp[maxn][maxn];
ll sum[maxn][maxn];int main() {while(~scanf("%d",&n)) {for(int i = 1;i <= n;++i) {scanf("%d",&a[i]);dp[i][i] = 0;}for(int i = 1;i <= n;++i) {sum[i][i] = a[i];for(int j = i+1;j <= n;++j)sum[i][j] = sum[i][j-1]+a[j];}for(int len = 2;len <= n;++len) {for(int i = 1,j;i+len-1 <= n;++i) {j = i+len-1;dp[i][j] = dp[i][i]+dp[i+1][j]+sum[i][i]*sum[i+1][j];for(int k = i;k < j;++k) {dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][k]*sum[k+1][j]);}}}printf("%lld\n",dp[1][n]);}
}