本文主要是介绍元素共鸣：深层次的唤醒，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
在提瓦特大陆上，有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;
}
这篇关于元素共鸣：深层次的唤醒的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
