UVA 10003 -Cutting Sticks ( dp, Knuth Optimization )

UVA 10003 -Cutting Sticks ( dp, Knuth Optimization )

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digits    0123456789012345678 ///
#define MX     53
#define inf    1000000010
#define MD     1000000007LL
#define eps    1e-9
///===============================///

int len,n,ar[MX],dp[MX][MX];
int opt[MX][MX]; ///Optimal Cut-point for l to r;

int go(int l,int r){
    if(l+2==r)return (ar[r]-ar[l]);
    if(l>=r || l+1==r)return 0;
    int &ret=dp[l][r];
    if(ret!=-1) return ret;
    ret=inf;
    go(l,r-1);
    go(l+1,r);
    int k1=opt[l][r-1];
    int k2=opt[l+1][r];
    for(int i=k1;i<=k2;i++){
        int tmp=(ar[r]-ar[l]+go(l,i)+go(i,r));
        if( ret>tmp ){
            ret=tmp;
            opt[l][r]=i;
        }
    }
    return ret;
}

int main() {
    int tc,cs=1,i,j,k,x;
    while( S(len)==1 && len ){
         S(n);
         ar[0]=0;
         for(i=1;i<=n;i++){
            S(ar[i]);
         }
         ar[n+1]=len;
         for(i=0;i<=n-1;i++){
            opt[i][i+2]=i+1;
            opt[i][i+1]=i;
         }
         SET(dp);
         int ans=go(0,n+1);
         printf("The minimum cutting is %d.\n",ans);
    }
    return 0;
}