UVa 10003 Cutting Sticks

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / hackerrank / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int dp[55][55], arr[55];

int func(int l, int r)
{
    if(r-l==1) return 0;

    int &ret=dp[l][r];
    if(ret!=-1) return ret;

    ret=INT_MAX;
    for(int i=l+1;i<r;i++)
        //ret=min(ret, func(l, i)+func(i, r)+arr[r]-arr[l]);
        {
            int cost=func(l, i)+func(i, r)+arr[r]-arr[l];
            if(ret>cost) ret=cost;
        }
    return ret;
}

int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);
    int kk=1, tc, n, m, i;
    //string s;
    //cin>>tc;
    while(scanf("%d", &n)==1)
    {
        if(!n) break;
        //cin>>m;
        scanf("%d", &m);
        for(i=1;i<=m;i++) scanf("%d", &arr[i]);//cin>>arr[i];
        arr[m+1]=n;
        arr[0]=0;
        SET(dp);
        //cout<<func(0, m+1)<<"\n";
        printf("The minimum cutting is %d.\n", func(0, m+1));
    }

    return 0;
}