Tuyên bố vấn đề
Cho N số học sinh và một mảng biểu diễn hiệu của học sinh. Trường học đã quyết định cung cấp cho họ bông làm giá. Tuyệt vời, trường học muốn tiết kiệm tiền, vì vậy họ giảm thiểu tổng số lần cần làm sạch sẽ bằng cách áp đặt các ràng buộc sau -
- Tất cả học sinh ít nhất phải có một con thú bông
- Nếu hai học sinh ngồi cạnh nhau thì học sinh nào có điểm cao hơn phải nhận được nhiều hơn
- Nếu hai sinh viên có cùng điểm thì họ được phép nhận số lần chấm khác nhau
Ví dụ
Giả sử có 3 sinh viên và điểm thu được được biểu diễn trong mảng là -
arr[] = {2, 3, 3}
So, total number of teddies to be distributed:
{1, 2, 1} i.e. 4 teddies Thuật toán
Vấn đề này có thể được giải quyết bằng cách sử dụng lập trình động như sau -
1. Create a table of size N and initialize it with 1 as each student must get atleast one teddy 2. Iterate over marks array and perform below step: a. If current student has more marks than previous student then: i. Get the number of teddies given to the previous student ii. Increment teddie count by 1 b. If current student has lesser marks than previous student then: i. Review and change all the values assigned earlier
Ví dụ
#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int teddieDistribution(int *marks, int n) {
int table[n];
fill(table, table + n, 1);
for (int i = 0; i < n - 1; ++i) {
if (marks[i + 1] > marks[i]) {
table[i + 1] = table[i] + 1;
} else if (marks[i] > marks[i + 1]) {
int temp = i;
while (true) {
if (temp >= 0 && (marks[temp] >
marks[temp + 1])) {
if (table[temp] >
table[temp + 1]) {
--temp;
continue;
} else {
table[temp] =
table[temp + 1] + 1;
--temp;
}
} else {
break;
}
}
}
}
int totalTeddies = 0;
for (int i = 0; i < n; ++i) {
totalTeddies += table[i];
}
return totalTeddies;
}
int main() {
int marks[] = {2, 6, 5, 2, 3, 7};
int totalTeddies = teddieDistribution(marks,
SIZE(marks));
cout << "Total teddies to be distributed: " <<
totalTeddies << "\n";
return 0;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra tiếp theo -
Total teddies to be distributed: 12