描述
在提瓦特大陆上，有N座由原石构成的神秘石柱，它们依次排列，编号为1，2，3，…，N。
每座石柱都蕴含着不同程度的元素能量，这种能量的强度可以用一个整数来量化。冒险者们面临着一个更加艰巨的任务：为了唤醒深层次的神之眼，他们不仅需要将这些原石石柱合而为一，而且在这一过程中，每一次移动需要选择连续的k堆石柱进行合并，释放出强大的元素共鸣。
每次合并连续的k堆石柱的过程中会释放出一定量的元素能量，其值等于这k堆石柱能量值的总和。合并后，这些石柱就会形成一座新的更大的石柱，而与这些石柱原先相邻的石柱将与新形成的石柱相邻。选择不同的k值和合并顺序会导致不同的总能量释放量。
冒险者们如何选择合并的连续石柱数量k以及合并的顺序，才能使释放的元素能量总量最小，以尽可能节约能量唤醒深层次的神之眼。
输入
- 第一行一个数N，表示原石石柱的数量N (1 ≤ N ≤ 30)。
- 第二行N个数，表示每座石柱的元素能量值(每个值均不超过1000)。
- 第三行一个数k，表示每次移动时，必须合并的连续石柱的数量 (2 ≤ k ≤ N)。
输出
输出一个整数，表示能量释放的最小总量。如果无法将石柱合而为一，则返回-1.
输入样例 1
4
1 3 5 2
2输出样例1
22
思路：
dp[i][j][t] 存储将第i个到第j个石头合并为t堆所需的最少能量
dp[i][j][t]=min(dp[i][m][1]+dp[m+1][j][t-1]+sum[j]−sum[i−1])
代码实现
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int stelae[35]={0};
int sum[35]={0};
int N,k;
//f[i][j][k]合并i到j个石柱并选择连续k个合并
class solution
{
public:
solution(int N,int k)
{
if((N-1)%(k-1)!=0)
{
cout<<-1<<endl;return;
}
vector<vector<vector<int>>> dp(N+1,vector<vector<int>>(N+1,vector<int>(k+1,INT_MAX)));
for(int len=1;len<=N;len++)
{
for(int l=1;l<=N-len+1;l++)
{
int r=l+len-1;
if(len==1)
{
dp[l][r][1]=0;continue;
}
for(int t=2;t<=k;t++)
{
for(int p=l;p<r;p+=k-1)
{
dp[l][r][t]=min(dp[l][r][t],dp[l][p][1]+dp[p+1][r][t-1]);
}
}
dp[l][r][1]=min(dp[l][r][1],dp[l][r][k]+sum[r]-sum[l-1]);
}
}
if (dp[1][N][1] == INT_MAX) {
cout << -1 << endl;
} else {
cout << dp[1][N][1] << endl;
}
}
};
int main()
{
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>stelae[i];
sum[i]=sum[i-1]+stelae[i];
}
cin>>k;
solution p(N,k);
return 0;
}