Видях доста интересни кодове тук и реших да добавя нещо и от мен ...
представлява задача от олимпиадата от май'06 ...
Условие
Метален прът трябва да бъде нарязан на няколко парчета. Цената в лева за извършване на едно отрязване е равна на дължината на рязания прът в метри. В даден момент може да бъде правен само един разрез. Различни стратегии за нарязване водят до различна цена.
Например да разгледаме прът с дължина 10 метра, който трябва да бъде нарязан във 2-рия, 4-тия и 7-мия метър. Бихме могли да извършим това като направим най-напред разрез в 2-ри метър, после в 4-ти метър и накрая 7-ми метър. Това струва 10 + 8 + 6 = 24 лева. Друг подход може да бъде да отрежем първо в 4-ти метър, после във 2-ри и в 7-ми метър. Сега цената е 10 + 4 + 6 = 20 лева.
Да се напише програма, която пресмята минималната цена на нарязване на прът с дадена дължина.
CODE1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int l,c;
cout << "Length: ";
cin >> l;
cout << "Number of the cuts: ";
cin >> c;
vector <int> i(c);
for (int a = 0; a < c; a++)
{
cout << "Cut position no." << a+1 << ":";
cin >> i[a];
}
long excl = 1;
for(int a = 1; a < c; excl *= (a++)+1) ;
int* endprice;
endprice = new int[excl];
for(int a = 0; a < excl; endprice[a++] = 0);
for(int a = 0; a < excl; a++)
{
bool* graph;
graph = new bool[l+1];
for(int b = 0; b < l+1; graph[b++] = true);
graph[0] = graph[l] = false;
cout << "nTesting the combination:" << endl;
for(int b = 0; b < c; cout << i[b++] << "t");
for(int b = 0; b < c; b++)
{
int price = 2;
int cc = i[b], tc = i[b]; graph[cc] = false;
while(graph[--tc]) price++;
tc = cc;
while(graph[++tc]) price++;
endprice[a] += price;
}
cout << "nPrice for cut no." << a+1 << " is: " << endprice[a];
cout << endl;
delete[] graph;
next_permutation(i.begin(),i.end());
}
int mv = endprice[0];
for(int a = 1; a < excl; a++)
{
if (endprice[a] < mv)
mv = endprice[a];
}
cout << "The minimum price is: " << mv << endl;
delete[] endprice;
system("pause");
return EXIT_SUCCESS;
} |
