<题目链接>
题目大意：
现在有n堆石子，第i堆有ai个石子。现在要把这些石子合并成一堆，每次只能合并相邻两个，每次合并的代价是两堆石子的总石子数。求合并所有石子的最小代价。
Input
第一行包含一个整数$ T（T<=50）$，表示数据组数。
每组数据第一行包含一个整数$ n（2<=n<=100）$，表示石子的堆数。
第二行包含n个正整数$ ai（ai<=100）$，表示每堆石子的石子数。
Output
每组数据仅一行，表示最小合并代价。
Sample Input
2
4
1 2 3 4
5
3 5 2 1 4
Sample Output
19
33 解题分析：
区间DP经典题，比较暴力，O(n^3)暴力枚举所有状态，然后进行转移。
#include <bits/stdc++.h>
using namespace std; #define N 105
#define rep(i,s,t) for(int i=s;i<=t;i++)
const int INF = 0x3f3f3f3f;
int dp[N][N],cost[N][N],val[N]; int main(){
int T;scanf("%d",&T);while(T--){
int n;cin>>n;
rep(i,,n)cin>>val[i],cost[i][i]=val[i];
rep(i,,n) rep(j,,n) {
dp[i][j] = (i==j?:INF);
}
for(int len=;len<=n;len++){ //枚举区间长度
for(int i=;i+len-<=n;i++){ //枚举起点i
int j=i+len-; //j为终点
for(int k=i;k<j;k++){
cost[i][j]=cost[i][k]+cost[k+][j];
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]+cost[i][j]);
}
}
}
printf("%d\n",dp[][n]); //dp[i][j]表示[i,j]区间内合并石子的最小代价
}
}
2019-02-18