ZOJ 2860 Breaking Strings

///     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[1005][1005], arr[1005], bm[1005][1005];

/*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;
        CLR(dp);
        for(int i=0;i<=m+1;i++) bm[i][i]=i;

        for(int i=1;i<=m;i++)
        {
            for(int j=1;i+j<=m+1;j++)
            {
                int mn=INT_MAX, pos;
                for(int k=bm[j][i+j-1];k<=bm[j+1][i+j];k++)
                    if(mn > (dp[j][k]+dp[k+1][i+j]+arr[i+j]-arr[j-1]))
                        //printf("done\n");
                        mn=(dp[j][k]+dp[k+1][i+j]+arr[i+j]-arr[j-1]), pos=k;
                bm[j][i+j]=pos;
                dp[j][i+j]=mn;
            }
        }
        //cout<<func(0, m+1)<<"\n";
        //printf("The minimum cutting is %d.\n", func(0, m+1));
        printf("%d\n", dp[1][m+1]);
    }

    return 0;
}