UVa - 10003 - Cutting Sticks

10003.cpp

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define endl '\n'
#define PB push_back

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int oo = ~(1<<31);

int n;
int T[57];
int dp[1007][1007];

int f(int i, int j) {

    int &r = dp[i][j];
    if(~r) return r;

    r = oo;
    for(int k=0; k<n; k++) {
        if(T[k] < j && T[k] > i)
            r = min(r, f(i, T[k]) + f(T[k], j) + (j - i));
    }

    if(r == oo) r = 0;
    return r;
}

int main() {
    #ifndef CBDAVIDES
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    #endif

    int l;
    while(cin >> l && l) {
        cin >> n;
        for(int i=0; i<n; i++) cin >> T[i];
        memset(dp, -1, sizeof dp);
        cout << "The minimum cutting is " << f(0, l) << ".\n";
    }

    return 0;
}