#DP #NestedRanges #UVa #Solved

10003 - Cutting Sticks.cpp

//https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944
#include <bits/stdc++.h>
 
#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)
 
using namespace std;
 
const int OO = (int)1e7;
const int MAX = 55;
int l, n;
int a[MAX];
int cache[MAX][MAX];
 
//TLE Solution
/*int minCut(int s, int e, int is, int ie) {
    if(s==e || is >= ie)
        return 0;
 
    if(cache[is][ie]!= -1)
        return cache[is][ie];
    int ret = OO;
    cout << e-s+1 << endl;
    getchar();
    for(int j = is; j<ie ; j++) {
            int c = a[j];
            ret = min(ret, minCut(s, c, is, j) + minCut(c+1, e, j+1, ie) + (e-s+1));
    }
    if(ret == OO)
        ret = 0;
    return (cache[is][ie] = ret);
}*/
 
int minCut2(int s, int e, int is, int ie) {
  //  cout << s << " " << e << " " << is << " " << ie << endl;
    if(is > ie || s == e)
        return 0;
 
    int &ret = cache[is][ie];
    if(ret != -1)
        return ret;
    ret = OO;
    for(int i = is; i<=ie; i++) {
        int c = a[i];
        ret = min(ret, minCut2(s, c, is, i-1)+minCut2(c+1, e, i+1, ie)+(e-s+1));
    }
 
    return ret;
}
 
int main() {
    while(cin>>l && l) {
        clr(cache, -1);
        cin>>n;
        int x;
        for(int i=1; i <=n;i++) {
            cin>>a[i];
        }
        cout << "The minimum cutting is " << minCut2(1, l, 1, n) << ".\n";
    }
    return 0;
}