segment cuts.cpp

#include <vector>
#include <list>
using namespace std;

// N - длина стержня, costs[i] - стоимость отрезка длины i+1
vector<size_t> GetCuts(size_t N, const vector<int>& costs) {
	// элемент односвязного списка
	struct Node {
		size_t cutlength;
		list<Node>::iterator next;
		Node(size_t cutlength, const list<Node>::iterator& next) : cutlength(cutlength), next(next) {}
	};
	// буфер для элементов односвязного списка
	list<Node> memory;
	// для каждой длины стержня определяем наилучшее приближение отрезками
	vector<pair<int, list<Node>::iterator>> trace;	// length-1 => cost, one way list of cuts
	trace.reserve(N);
	// инициализация начального приближения
	for (size_t i = 0; i < N; ++i) {
		if (i < costs.size())
			trace.push_back(make_pair(costs[i], memory.insert(memory.end(), Node(i, memory.end()))));
		else
			trace.push_back(make_pair(0u, memory.end()));
	}
	// К каждому начальному приближению пытаемся прибавить отрезок каждой из длин.
	// Одного прохода по массиву достаточно, т.к. на следующем шаге для отрезков меньшей длины
	// мы уже получили наилучшее приближение.
	for (size_t j = 0; j < N; ++j) {
		auto &item = trace[j];
		for (size_t i = 0; i < costs.size(); ++i) {
			auto new_length = j + i + 1;				// новая длина отрезка
			if (new_length >= N)						// если больше допустимой, то продолжать нет смысла, т.к. на следующих шагах мы будем получать бОльшие длины
				break;
			auto new_cost = item.first + costs[i];		// новая стоимость
			auto &new_set = trace[new_length];			// запись <стоимость, список составных частей> для отрезка длины new_length
			if (new_cost > new_set.first) {				// если мы нашли лучшее приближение, то заменяем текущее на лучшее
				new_set.first = new_cost;
				new_set.second = memory.insert(memory.end(), Node(i, item.second)); // добавляем элемент в начало связного списка
			}
		}
	}
	// подготовим и вернём результат
	vector<size_t> result(N, 0);
	for (auto it = trace[N - 1].second; it != memory.end(); it = it->next)
		++result[it->cutlength];
	return result;
}

#include <iostream>
int main() {
	//                         стоимости
	//                длина    1    2  3  4  5  6  7  8  9 10    11
	auto cuts = GetCuts(11u, { 0, 202, 0, 0, 0, 0, 0, 0, 0, 0, 1100 });
	for (size_t i = 0; i < cuts.size(); ++i)
		if (cuts[i] != 0)
			cout << "cuts of length " << i + 1 << " -> " << cuts[i] << endl;
    return 0;
}