Problem 64: Minimum Cost to Merge Stones
Problem Statement: Given an array representing piles of stones and an integer k, determine the minimum cost to merge the stones into one pile. Merging exactly k consecutive piles costs the sum of their weights. If it is impossible, output -1.
Input
The first line contains two integers n and k. The second line contains n space-separated integers representing the weight of each pile.
Output
Print the minimum cost to merge all stones into one pile, or -1 if impossible.
Examples
Input:
4 3
3 2 4 1
Output:
null
Solution Explanation
Use dynamic programming where dp[i][j] represents the minimum cost to merge stones from i to j into a certain number of piles. The transition considers merging k piles at a time. Check feasibility via (n-1) mod (k-1).
Solution in C++
#include
#include
#include
#include
using namespace std;
const long long INF = 1000000000000000000LL;
int main(){
int n, k;
cin >> n >> k;
vector stones(n);
for(int i = 0; i < n; i++)
cin >> stones[i];
if((n - 1) % (k - 1) != 0){
cout << -1 << "\n";
return 0;
}
vector> dp(n, vector(n, 0));
vector pre(n + 1, 0);
for (int i = 0; i < n; i++)
pre[i + 1] = pre[i] + stones[i];
for (int len = k; len <= n; len++){
for (int i = 0; i + len - 1 < n; i++){
int j = i + len - 1;
dp[i][j] = INF;
for (int mid = i; mid < j; mid += (k - 1)){
dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
}
if((len - 1) % (k - 1) == 0){
dp[i][j] += pre[j + 1] - pre[i];
}
}
}
cout << dp[0][n - 1] << "\n";
return 0;
}