题目传送门
Problem Description
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
Input
有多组测试数据，输入到文件结束。 每组测试数据第一行有一个整数n，表示有n堆石子。 接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开
Output
输出总代价的最小值，占单独的一行
Sample Input
3
1 2 3
7
13 7 8 16 21 4 18
Sample Output
9
239
题解：
区间DP模板题用dp[i][j]来表示合并第i堆到第j堆石子的最小代价。那么状态转移方程为 ： dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+cost[i][j]); cost维护前缀和，有cost(i, j) = cost[j] - cost[i-1];
AC-Code：
#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <fstream>
#include <set>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std
;
typedef long long ll
;
const int INF
= 0x3f3f3f;
const int MAXN
= 1e2 + 10;
int max(int a
, int b
, int c
) {
int t
= a
> b
? a
: b
;
return t
> c
? t
: c
;
}
int dp
[MAXN
][MAXN
];
int a
[MAXN
];
int cost
[MAXN
];
int main() {
int n
;
while (cin
>> n
) {
memset(dp
, INF
, sizeof dp
);
cost
[0] = 0;
for (int i
= 1; i
<= n
; i
++) {
cin
>> a
[i
];
cost
[i
] = cost
[i
- 1] + a
[i
];
dp
[i
][i
] = 0;
}
for (int len
= 2; len
<= n
; len
++)
for (int i
= 1; i
<= n
; i
++) {
int j
= i
+ len
- 1;
if (j
> n
)
break;
for (int k
= i
; k
< j
; k
++)
dp
[i
][j
] = min(dp
[i
][j
], dp
[i
][k
] + dp
[k
+ 1][j
] + cost
[j
] - cost
[i
- 1]);
}
cout
<< dp
[1][n
] << endl
;
}
return 0;
}
