CSU 1592 石子合并 (经典题)【区间DP】

<题目链接>

题目大意：

现在有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,1,n)cin>>val[i],cost[i][i]=val[i];
        rep(i,1,n) rep(j,1,n) {
            dp[i][j] = (i==j?0:INF);
        }
        for(int len=1;len<=n;len++){       //枚举区间长度
            for(int i=1;i+len-1<=n;i++){   //枚举起点i
                int j=i+len-1;      //j为终点
                for(int k=i;k<j;k++){
                    cost[i][j]=cost[i][k]+cost[k+1][j];
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+cost[i][j]);
                }
            }
        }
        printf("%d
",dp[1][n]);     //dp[i][j]表示[i,j]区间内合并石子的最小代价
    }
} 

2019-02-18