imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:03Z

New page

#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;
}

CuttingSticks/김상섭 - Revision history

imported>Unknown at 05:23, 7 February 2021