Weighted Rod Cutting
National Olympiad — Regional round
Submission name: rod.cpp
Problem summary
A rod consists of N consecutive unit pieces with positive weights. To cut a current segment into two at a unit boundary, pay the total weight of that segment. Continue until every piece has length one. Minimize the total weight lifted. Pieces must retain their original order.
Input
N, then the N positive integer unit weights.
Output
Minimum total cutting cost.
Constraints
1≤N≤999; total weight <999999.
Worked example
An independently prepared example for this explanation.
Input
3 2 4 3
Output
15
Solution analysis
- Let dp[l][r] be the minimum cost for the consecutive pieces l…r. The first cut k costs their total weight plus dp[l][k]+dp[k+1][r].
- Prefix sums give interval weights in constant time. Base cases dp[i][i]=0.
- Use Knuth optimization: positive additive interval weights satisfy monotonicity and the quadrangle inequality, so an optimal split lies between opt[l][r−1] and opt[l+1][r].
Why it works
Every cutting process has a first cut and two independent subproblems, proving the recurrence. Additive interval weights satisfy w(a,c)+w(b,d)=w(a,d)+w(b,c) for a≤b≤c≤d and are nondecreasing under inclusion, which permits the monotone split bounds of Knuth optimization.
Watch out. An unrestricted Huffman merge is wrong because only consecutive pieces can be grouped. Use 64-bit costs.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<climits>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<long long>s(n+1);
for(int i=1;i<=n;i++){
long long w;
cin>>w;
s[i]=s[i-1]+w;
}
vector<vector<long long>>d(n+2,vector<long long>(n+2));
vector<vector<int>>o(n+2,vector<int>(n+2));
for(int i=1;i<=n;i++){
o[i][i]=i;
}
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
d[l][r]=LLONG_MAX;
// Knuth bounds avoid trying every possible first cut.
for(int k=o[l][r-1];k<=min(r-1,o[l+1][r]);k++){
long long z=d[l][k]+d[k+1][r]+s[r]-s[l-1];
if(z<d[l][r]){
d[l][r]=z;
o[l][r]=k;
}
}
}
}
cout<<d[1][n]<<'\n';
}