Cutting Sticks/김상섭

No older revisions available

~cpp
#include <iostream>
using namespace std;
#include <vector>

int main()
{
	int length, tokennum, token, l, i, j, m;
	vector< vector<int> > Data;
	vector<int> temp;
	
	cin >> length;
	while(length)
	{
		cin >> tokennum;
		temp.push_back(0);
		for(int i = 0 ; i < tokennum; i++)
		{
			cin >> token;
			temp.push_back(token);
		}
		temp.push_back(length);
		Data.push_back(temp);
		temp.clear();

		cin >> length;
	}

	int store[51][51];
	for(vector< vector<int> >::iterator k = Data.begin(); k != Data.end(); k++)
	{
		temp = *k;
		tokennum = temp.size() - 1;
		for(j = 0; j < tokennum ; j++)
		{
			store[j][j+1] = 0;
		}

		for(j = 0; j < tokennum - 1; j++)
		{
			store[j][j+2] = temp[j+2] - temp[j];
		}

		for(m = 3; m < tokennum + 1; m++)
		{
			for(i = 0; i + m < tokennum + 1; i++ )
			{
				int temp1,min = INT_MAX;
				for(l = i+1; l < i + m; l++ )
				{
					temp1 = store[i][l] + store[l][i+m];
					if(min > temp1)
						min = temp1;
					store[i][i+m] = min + temp[i+m] - temp[i];
				}
			}
		}
		cout << "The minimum cutting is " <<store[0][tokennum] << ".\n";		
	}	
	return 0;
}