UVa : 10003 (Cutting Sticks)



// http://uva.onlinejudge.org/external/100/10003.html

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
using namespace std;

int l, n;
int c [50 + 3];
int dp [50 + 3] [50 + 3];

int bktk (int s, int e)
{
    if ( s + 1 == e ) return 0;

    if ( dp [s] [e] != -1 )
        return dp [s] [e];

    int cost = 0;
    int minimum = INT_MAX;

    for ( int i = s + 1; i < e; i++ ) {
        cost = bktk (s, i) + bktk (i, e) + c [e] - c [s];
        if ( cost < minimum ) minimum = cost;
    }

    return dp [s] [e] = minimum;
}

void reset ()
{
    for ( int i = 0; i < 53; i++ ) {
        for ( int j = 0; j < 53; j++ )
            dp [i] [j] = -1;
    }
}

int main ()
{
    while ( scanf ("%d", &l) && l ) {
        scanf ("%d", &n);

        for ( int i = 1; i <= n; i++ )
            scanf ("%d", &c [i]);

        c [0] = 0;
        c [n + 1] = l;

        reset ();

        printf ("The minimum cutting is %d.\n", bktk (0, n + 1));
    }

	return 0;
}

// @END_OF_SOURCE_CODE

One thought on “UVa : 10003 (Cutting Sticks)

  1. This question has been asked in one of the interview(zenxxx). Here is the solution in swift language.

    override func viewDidLoad() {
    super.viewDidLoad()
    // Do any additional setup after loading the view, typically from a nib.

    var arr = [12, 5, 7, 6,56];
    self.getMinNumberofIterationsForCuttingSticksProblem(&arr);

    }

    func getMinNumberofIterationsForCuttingSticksProblem(inout array: [Int]) -> Int {

    if array.count == 1 {
    return 0;
    }
    var iterations = 0;
    repeat {
    iterations = iterations + 1 ;
    array = array.filter(){$0 > 0}
    debugPrint(“No \(iterations) iteration array elements \(array)”)

    if array.count == 1 {
    debugPrint(“last element \(array[0])”)
    return iterations;
    }
    let min = [array.sort(){$1>$0}][0][0]
    array = array.map{ $0 – min }

    }while( (array.count != 1 || array.count
    != 0 ))
    return iterations
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s