https://ac.nowcoder.com/acm/contest/8688/E
给定一串数字a b c d e，删除某个数的代价是左右和的平方，eg: 删b，代价是(a+b+c)2 ，求最小代价
解： dp[i][j]代表从i~j的最小代价，不会删除i和j（因为靠边凑不了3个）
dp[i][j]=min(dp[i][j],dp[i][h]+dp[h][j]+(a[i]+a[h]+a[j])2)
注意dp时从区间长度开始递增
1 #include<cstdio>
2 #include<cstdlib>
3 #include<algorithm>
4 #include<cstring>
5 #include<queue>
6 #include<iostream>
7 #include<vector>
8 #include<iostream>
9 using namespace std;
10 #define ll long long
11 int const N=120;
12 int const INF=2147483647;
13 ll a[N],f[N][N];
14 int n;
15 int main(){
16 while (scanf("%d",&n)!=EOF) {
17 for (int i=0;i<n;i++)
18 for (int j=0;j<n;j++)
19 f[i][j]=INF;
20 for (int i=0;i<n;i++){
21 scanf("%lld",&a[i]);
22 f[i][i+1]=0;
23 }
24 for (int h=3;h<=n;h++)
25 for (int i=0;i<=n-h;i++){
26 int j=i+h-1;
27 for (int k=i+1;k<j;k++){
28 ll temp=(a[i]+a[j]+a[k])*(a[i]+a[j]+a[k]);
29 f[i][j]=min(f[i][j],temp+f[i][k]+f[k][j]);
30 }
31 }
32 printf("%lld\n",f[0][n-1]);
33 }
34 return 0;
35 }