Bài tập c++ về sắp xếp các đoạn nối tiếp nhau

“tìm số lượng tối đa K đoạn thẳng”, là đếm số lượng nhóm K đoạn gối nhau liên tiếp, hay là tìm K lớn nhất?

đề bài yêu cầu tìm k lớn nhất

Pasted image1366x768 76.8 KB

• sort lại tăng dần theo điểm kết thúc b_j
• sau đó sử dụng quy hoạch động: F[i] là số đoạn liên tiếp dài nhất gối nhau, mà vị trí kết thúc của đoạn cuối cùng là i. Ban đầu F[i] = 0 với mọi i. Sau đó với mỗi đoạn [a_j, b_j]. Lúc đó ta có 2 trường hợp:
  • Nếu không chọn đoạn này, F[b_j] không đổi.
  • Nếu chọn đoạn: F[b_j] = F[a_j - 1] + 1 (nếu nó là đoạn đầu tiên trong các đoạn gối nhau, thì hiển nhiên F[a_j - 1] = 0 và F[b_j] = 1 tức chính nó).
  • Vậy tổng quát là F[b_j] = (F[b_j], F[a_j - 1] + 1)
• Để lấy kết quả thì duyệt lại trên mảng F và tìm F[i] lớn nhất.
  Lưu ý: nếu sử dụng pascal thì có thể dùng trực tiếp dữ liệu input. Nếu sử dụng các ngôn ngữ như C++, Java thì trước khi thực hiện DP, cần dời trục tọa độ các đoạn này, để các đoạn đoạn [a_j, b_j] đều không âm.

Mình k phải chuyên ngành IT… Xin hỏi học mấy cấu trúc giải thuật và dữ liệu đó có thể làm gì khi lập trình soft. Mình học điện, làm nhúng, mới bước chân vô nghề. Mong các bác chỉ giáo. TKS

Những thuật toán nói chung thì sẽ giúp bạn tăng khả năng tư duy giải quyết vấn đề.
Ngoài ra thì một số thuật toán nâng cao có thể áp dụng để giải quyết những bài toán cụ thể: ví dụ bài toán tìm đường, bài toán lập lịch điều phối giao hàng, lên thời khóa biểu, …
Nếu bạn làm nhúng về điện thì sẽ ít gặp thuật toán, chứ nếu mình nhớ k nhầm, nếu nhúng device, nhúng về các smart device thì dùng thuật toán nhiều lắm