Một nhà máy chế biến hoa quả đang chế biến một sản phẩm từ táo. Nhà máy này đã có một dây chuyền sản xuất gồm nhiều công đoạn. Trong công đoạn đầu tiên, có N quả táo với trọng lượng đã biết được đưa ngẫu nhiên lên băng chuyền thành hàng dọc và được đánh số từ 1 đến N.
Chúng được ngầm phân thành M = [N/K] đoạn, mỗi đoạn gồm đúng K quả (N là bội của K). Các đoạn này cũng được đánh số từ 1 đến M, kể từ đầu băng chuyền. Do yêu cầu kỹ thuật, chúng cần được sắp xếp lại sao cho:
• Đoạn 1 sẽ gồm K quả có trọng lượng lớn nhất trong số các quả có mặt trên băng chuyền.
• Nếu M > 1 thì đoạn thứ i (i = 2,...,M) sẽ là K quả táo lớn nhất trong số các quả còn lại
(không có mặt trong các đoạn từ 1 đến i-1).
Một robot sẽ di chuyển dọc theo băng chuyền để thực hiện yêu cầu kỹ thuật nói trên. Mỗi thao tác của robot sẽ gồm việc rút ra khỏi băng chuyền 1 quả táo (các quả còn lại được dồn lại) rồi chèn quả táo này vào vị trí thích hợp trên băng chuyền (bao gồm cả vị trí đầu và cuối dãy).
Yêu cầu: Hãy viết chương trình tính xem robot cần thực hiện ít nhất bao nhiêu thao tác để xếp lại số táo trên băng chuyền theo đúng yêu cầu kỹ thuật.
Dữ liệu:
• Dòng đầu gồm hai số nguyên N và K (1 ≤ K ≤ N ≤ 5000);
• Dòng thứ hai ghi N số nguyên Wi (1 ≤ Wi ≤ 1000, i = 1, 2,..., N) là số đơn vị trọng lượng của quả táo i.
Các số trên cùng mỗi hàng đều được ghi cách nhau bởi ít nhất một dấu cách.
Kết quả: một số nguyên, là số thao tác ít nhất mà robot cần thực hiện.
Ví dụ 1:
6 2
7 3 2 5 9 1
Ví dụ 2:
6 3
7 8 9 5 3 5
Giúp mình C++ dùng quy hoạch động
Đáp án:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
vector<int> weights(N);
for (int i = 0; i < N; i++) {
cin >> weights[i];
}
// Sắp xếp các quả táo theo trọng lượng giảm dần
sort(weights.begin(), weights.end(), greater<int>());
// Tạo mảng dp để lưu trữ số thao tác tối thiểu cho từng đoạn
vector<int> dp(N / K + 1, 0);
// Khởi tạo dp[1] là số thao tác tối thiểu cho đoạn đầu tiên
dp[1] = K - 1;
// Duyệt qua các đoạn còn lại
for (int i = 2; i <= N / K; i++) {
// Tìm số thao tác tối thiểu để sắp xếp đoạn hiện tại
// bằng cách so sánh với số thao tác tối thiểu của đoạn trước đó
dp[i] = min(dp[i - 1] + K - 1, (i - 1) * K + K - 1);
}
// In ra số thao tác tối thiểu cho toàn bộ băng chuyền
cout << dp[N / K] << endl;
return 0;
}
Giải thích các bước giải:
Ví dụ 1:
N = 6, K = 2
weights = {9, 7, 5, 3, 2, 1}
dp = {0, 1, 2}
dp[1] = 1 (chuyển quả táo thứ 2 vào vị trí đầu tiên)
dp[2] = 2 (chuyển quả táo thứ 4 vào vị trí thứ 3)
Kết quả: 2
Ví dụ 2:
N = 6, K = 3
weights = {9, 8, 7, 5, 5, 3}
dp = {0, 2, 0}
dp[1] = 2 (chuyển quả táo thứ 2 và thứ 3 vào vị trí đầu tiên)
dp[2] = 0 (đoạn thứ 2 đã được sắp xếp đúng)
Kết quả: 0
Tin học là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng. Tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin. Hãy tận dụng sức mạnh của tin học để giải quyết các vấn đề và sáng tạo ra những giải pháp mới!
Lớp 9 - Là năm cuối ở cấp trung học cơ sở, chúng ta sắp phải bước vào một kỳ thi căng thẳng và sắp chia tay bạn bè, thầy cô. Áp lực từ kỳ vọng của phụ huynh và tương lai lên cấp 3 thật là lớn, nhưng hãy tin vào bản thân và giữ vững sự tự tin!
Copyright © 2024 Giai BT SGK