Description
有n堆石子排成一圈，每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。
Input
第一行一个整数n(1 <= n <= 200)，表示石子堆数； 第二行n个整数a(1 <= a <= 100)，表示每堆石子的个数，这些石子首尾相接排成一圈。
Output
一个整数，表示最小总得分。
Sample Input
5
7 6 5 7 100
Sample Output
175
Source
Unknown
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eps 1e-9
#define pi acos(-1)
const int inf =
0x3f3f3f3f;
const int mod = 1e9+
7;
const int maxn =
1000 +
8;
int n, a[maxn], sum[maxn], dp[maxn][maxn], mi;
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >>
n;
sum[0] =
0;
for(
int i =
1; i <= n; i++
)
{
cin >>
a[i];
sum[i] += a[i] + sum[i -
1];
}
for(
int len =
1; len <= n; len++
)
{
for(
int i =
1; i <= n; i++
)
{
int en = (i + len) % n ==
0 ? n : (i + len) %
n;
int tmp;
if(i + len <=
n)
tmp = sum[i + len] - sum[i -
1];
else
tmp = sum[n] - sum[i -
1] + sum[(i + len) %
n];
dp[i][en] =
inf;
for(
int k =
0; k < len; k++
)
dp[i][en] = min(dp[i][en], dp[i][(i + k) % n ==
0 ? n : (i + k) % n] + dp[(i + k +
1) % n ==
0 ? n : (i + k +
1) % n][en] +
tmp);
}
}
mi = dp[
1][n];
for(
int i =
2; i <= n; i++
)
if(mi > dp[i][i -
1])
mi = dp[i][i -
1];
cout << mi <<
'\n';
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/11480394.html
相关资源：不能移动的石子合并问题（动态规划/C 实现）
