UVa 10003 - Cutting Sticks

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define F first
#define S second
typedef long long ll;
typedef vector< int > vi;
typedef vector< ll > V;
typedef map<int, int > mp;
#define debug cout << -1 << endl;
#define REP(i, a, b) for(int i=a; i<b; i++)
#define f0r(i, n) for (int i = 0; i < n; ++i)
#define fore(a, x) for (auto& a : x)
#define fori(i, a, b) for (int i = (a); i < (b); ++i)
#define pop pop_back
#define sz(a) (int)a.size()
const ll MOD = 1000000007;
const int INF = INT_MAX;
const int maxN = 2001;

int dx[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dy[] = {-1, -1, -1, 0, 0, 1, 1, 1};

int l, n;
int dp[55][55];
int cut[55];
int vis[55][55];
int dpF(int x, int y)
{
	int& ans = dp[x][y];
	if(vis[x][y]!=-1) return ans;
	if(y-x==1) return 0;
	for(int i=x+1; i<y; i++) {
		int cost = cut[y]-cut[x];
		ans = min(ans, dpF(x, i)+dpF(i, y)+cost);
		vis[x][y] = 1;
	}
	return ans;
}

void solve()
{
	while(cin >> l && l) {
		cin >> n;
		for(int i=1; i<=n; i++) {
			cin >> cut[i];
		}
		cut[0] = 0;
		cut[n+1] = l;
		memset(vis, -1, sizeof(vis));
		memset(dp, 0x3f3f3f, sizeof(dp));
		cout << "The minimum cutting is " << dpF(0, n+1) << ".\n";
	}
	return;
}

int main()
{
	//FastIO;
	//freopen("mowing.in","r",stdin);
	//freopen("mowing.out","w",stdout);
	int t;
	t = 1;
	//cin >> t;
	//cin.ignore();
	while(t--){
		solve();
	}
	return 0;
}