IEEE CodeBuddy | Week 4 | Vilas M & Akash Nair

rodcutting.cpp

typedef long long ll;
vector<int>ans;
vector<int>ar;
ll dp[1000][1000];
ll bestcut[1000][1000];
ll sol(int l,int r)
{
    ll good_cut;
    if(l + 1 >= r)  return 0;
    if(dp[l][r] != -1)
    return dp[l][r];
    dp[l][r] = LONG_MAX;
     for(ll i = l + 1; i < r; i++)
    {
        ll a = ar[r] - ar[l] + sol(l,i) + sol(i,r);
        if(a < dp[l][r])
        {
            dp[l][r] = a;
            good_cut = i;
        }
    }
    bestcut[l][r] = good_cut;
    return dp[l][r];
}
void mem(int l, int r){
    if(l + 1 >= r)  return;
    ans.push_back(ar[bestcut[l][r]]);
    mem(l,bestcut[l][r]);
    mem(bestcut[l][r],r);
}
vector<int> Solution::rodCut(int A, vector<int> &B) {
    B.push_back(A);
    B.insert(B.begin(),0);
    int n = B.size();
    ar.clear();
    for(int i = 0; i < n; i++)
        ar.push_back(B[i]);
    ans.clear();
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
            dp[i][j] = -1;
    }
    ll best = sol(0,n-1);
    mem(0,n-1);
    return ans;
}