Sáng kiến kinh nghiệm THPT: Sử dụng Quy hoạch động để giải quyết một số bài toán trong bồi dưỡng học sinh giỏi môn Tin học

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:61

Thêm vào BST

Báo xấu

19
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài tập trung nghiên cứu, tìm hiểu, phân tích từ 30 bài tập cơ bản đến nâng cao và 10 bài toán luyện tập dạng bài tập về quy hoạch động, để tìm ra nhiều cách làm khác nhau, đánh giá độ phức tạp, đo thời gian thực hiện chương trình, để so sánh tìm ra chương trình tối ưu nhất và dễ hiểu nhất trong các chương trình đã đưa ra.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Sử dụng Quy hoạch động để giải quyết một số bài toán trong bồi dưỡng học sinh giỏi môn Tin học

SỞ GD & ĐT NGHỆ AN SÁNG KIẾN KINH NGHIỆM Đề tài: SỬ DỤNG QUY HOẠCH ĐỘNG ĐỂ GIẢI QUYẾT MỘT SỐ BÀI TOÁN TRONG BỒI DƯỠNG HỌC SINH GIỎI MÔN TIN HỌC LĨNH VỰC: TIN HỌC Năm học 2022 – 2023 1
SỞ GD & ĐT NGHỆ AN TRƯỜNG THPT LÊ VIẾT THUẬT SÁNG KIẾN KINH NGHIỆM Tên đề tài: SỬ DỤNG QUY HOẠCH ĐỘNG ĐỀ GIẢI QUYẾT MỘT SỐ BÀI TOÁN TRONG BỒI DƯỠNG HỌC SINH GIỎI MÔN TIN HỌC Lĩnh vực: TIN HỌC Tác giả: Trần Thị Anh Thư Trần Diệu Thúy Tổ: Toán - Tin Năm học 2022 – 2023 2
ĐẶT VẤN ĐỀ I. Lý do chọn đề tài 1. Xuất phát từ xu hướng tuyển sinh của các trường Đại học có ngành học về Công nghệ thông tin. Hiện nay một số trường Đại học sử dụng kết quả kì thi học sinh giỏi tỉnh để làm một tiêu chí lựa chọn xét tuyển. Tin học lập trình là một môn học khó đối với học sinh THPT. Làm thế nào để học sinh hiểu, học tốt, yêu thích và tham gia tốt các kỳ thi học sinh giỏi Tin học là điều mà nhiều giáo viên dạy tin học trăn trở. Trong tin học, bài toán là một việc nào đó mà ta muốn máy tính thực hiện, để giải bài toán chúng ta cần có các thuật toán. Thuật toán là dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho từ input sau khi thực hiện dãy thao tác đó ta thu được output cần tìm của bài toán. Như vậy một bài toán có thể dùng rất nhiều thuật toán để giải quyết, vấn đề là chọn thuật toán nào hay phương pháp nào phù hợp với từng kiểu bài để đạt hiệu quả cao nhất. Chương trình Tin học phổ thông đã có một số thuật toán để giải một lớp bài toán nhất định như: các thuật toán Sắp xếp, tìm kiếm ...và một số phương pháp thiết kế thuật toán như: Chia để trị, tham lam, quy hoạch động... 2. Từ thực tế giảng dạy của bản thân chúng tôi nhận thấy việc nắm vững các thuật toán và áp dụng nó một cách linh hoạt trong các bài tập nhất định là không đơn giản. Khi nào thì chúng ta cần đến quy hoạch động? Đó là một câu hỏi rất khó trả lời. Không có một công thức nào cho các bài toán như vậy. Để có thể nhận dạng một bài toán có thể thực hiện với thuật toán này không phải dễ, ngoài ra để cài đặt được thuật toán hiệu quả nhất cũng đòi hỏi người lập trình nắm vững các phương pháp thiết kế thuật giải. 3. Trên cơ sở đó, chúng tôi trăn trở nghiên cứu đề tài “Sử dụng Quy hoạch động để giải quyết một số bài toán trong bồi dưỡng học sinh giỏi môn Tin học”. II. Đối tượng nghiên cứu Đề tài tập trung nghiên cứu, tìm hiểu, phân tích từ 30 bài tập cơ bản đến nâng cao và 10 bài toán luyện tập dạng bài tập về quy hoạch động, để tìm ra nhiều cách làm khác nhau, đánh giá độ phức tạp, đo thời gian thực hiện chương trình, để so sánh tìm ra chương trình tối ưu nhất và dễ hiểu nhất trong các chương trình đã đưa ra. III. Phương pháp nghiên cứu - Phương pháp nghiên cứu lí luận - Phương pháp thống kê, xử lí số liệu - Phương pháp đặt vấn đề - giải quyết vấn đề - Phương pháp phân tích, tổng hợp - Phương pháp Test 1
- Phương pháp thực nghiệm - Phương pháp so sánh đối chiếu IV. Cấu trúc của đề tài Phần một: Đặt vấn đề Phần hai: Nội dung Phần ba: Kết luận 2
NỘI DUNG I. Cơ sở của đề tài 1. Cơ sở lí luận 1.1. Khái niệm Quy hoạch động (dynamic programming) là kỹ thuật trong lập trình giúp đơn giản hóa hiệu quả việc chia bài toán lớn thành các bài toán con chồng chéo và cấu trúc con tối ưu. Những bài toán này thường có nhiều nghiệm đúng và mỗi nghiệm có một giá trị đánh giá. Do đó, cần tính toán nhiều lần và sử dụng lời giải của các bài toán con để tìm ra đáp án cho bài toán ban đầu. Khi muốn giải quyết một bài toán một cách nhanh nhất thì thuật toán này là một cách giải giúp tối ưu thời gian. Quy hoạch động này bao gồm bốn bước như sau:  Bước 1: Đặc trưng hóa cấu trúc của lời giải tối ưu.  Bước 2: Định nghĩa giá trị của lời giải tối ưu một cách đệ quy.  Bước 3: Tính trị của lời giải tối ưu theo kiểu từ dưới lên hoặc trên xuống.  Bước 4: Xây dựng lời giải tối ưu từ những thông tin đã được tính toán trên. Thay vì gọi đệ quy, thuật toán sẽ tính toán lời giải của các bài toán con trước tiên và lưu vào mảng bộ nhớ. Tiếp theo, sẽ dùng lời giải của bài toán con trong mảng đã tính trước đó để giải bài toán lớn theo công thức truy hồi. Công thức truy hồi là công thức thể hiện quan hệ giữa các bước trong một bài toán và kết quả của bước sau nhờ vào kết quả của các bước trước đó. Thuật toán này với ưu điểm chính là tiết kiệm thời gian tính toán thì cũng có một vài nhược điểm. Đầu tiên, việc tìm ra công thức truy hồi hay phân rã bài toán lớn yêu cầu phải suy nghĩ và phân tích thật kỹ càng. Điều này sẽ giúp bạn tránh được sự sai sót cũng như rủi ro phải tính lại từ đầu. Thứ hai là khó xử lý dữ liệu khi bảng lưu trữ yêu cầu mảng hai hoặc ba chiều. Cuối cùng, không phải bài toán tối ưu nào cũng có thể áp dụng giải bằng quy hoạch động. Bên cạnh đó, một bài toán tối ưu cũng có một số đặc điểm cần lưu ý dưới đây: Cần phân tách bài toán lớn thành nhiều bài toán con và kết hợp lời giải của các bài toán con để giải của bài toán lớn.  Bản chất của thuật toán là giải tất cả các bài toán con. Quy hoạch động không thể tiến hành được nếu không gian lưu trữ không đủ để phối hợp. Khi nào nên áp dụng thuật toán quy hoạch động? Điểm quyết định trong khi giải thuật toán này là cần tìm ra được công thức truy hồi cho từng trường hợp bài toán. Đối với một số bài toán thì dễ dàng có nhiều cách giải và giải bằng quy hoạch động nhưng chưa hẳn là giải pháp tối ưu. Mỗi bài toán 3
là mỗi kiểu khó khác nhau, không có một công thức chung cho tất cả các bài toán đó được. Vậy khi nào chúng ta nên áp dụng đến thuật toán này? Thường bài toán có hai tính chất này là bạn có thể sử dụng thuật toán quy hoạch động vào. Đó chính là bài toán con gối nhau và cấu trúc con tối ưu. Sử dụng thuật toán quy hoạch động khi nào? Bài toán con gối nhau Bài toán con gối nhau là bài toán nhỏ hơn và được chia từ bài toán ban đầu ra. Việc sử dụng lặp lại nhiều lần này, thuật toán sẽ lưu kết quả mà không cần tính lại, giúp bạn tiết kiệm rất nhiều thời gian. Việc giải một bài toán con nhiều lần thì không thể tránh khỏi việc trùng lời giải của các bài toán con. Khi các bài toán con không gối nhau thì việc áp dụng thuật toán này cũng bằng không. Quy hoạch động không thể tối ưu được với thuật toán tìm kiếm nhị phân. Lý do vì khi chia bài toán lớn thành các bài toán nhỏ và mỗi bài toán chỉ cần giải một lần mà không được gọi lại. Bài toán tính Fibonacci là ví dụ rất điển hình của bài toán con gối nhau. Bằng cách cộng fibonacci thứ n-1 và n-2 sẽ tính được số fibonacci thứ n. Bài toán con của số fibonacci thứ n chính là bài toán tính fibonacci n-1 và n-2. Công thức tính toán số Fibonacci được tính như sau: def fib(n): if n
con tối ưu có thể dễ dàng tính toán hoặc có khi không cần phải tính toán nữa. Các bài toán con tối ưu có thể sử dụng công thức truy hồi đưa vào thuật toán để tìm ra đáp án cuối cùng cho bài toán. Cấu trúc con tối ưu với quy trình ba bước mà bạn nên nắm rõ để có thể giải một bài toán nhanh chóng nhất:  Bước 1: Từ bài toán lớn chia thành các bài toán con nhỏ hơn.  Bước 2: Sử dụng phương pháp đệ quy để giải các bài toán con tối ưu.  Bước 3: Lấy kết quả tối ưu đã tính để có thể dễ dàng tìm lời giải tối ưu cho bài toán lớn trên. Bài toán có cấu trúc con tối ưu rất quan trọng, bởi nó cho phép bạn dựa vào các bài toán con đã giải để có lời giải cho bài toán lớn. Chúng ta sẽ không thể nào áp dụng thuật toán quy hoạch động nếu bài toán không có tính chất này. Các phương pháp trong quy hoạch động Trong quy hoạch động, chúng ta có thể sử dụng một trong hai cách để lưu trữ dễ dàng các giá trị đã tính như sau: Phương pháp từ trên xuống ( phương pháp ghi nhớ ) Phương pháp từ trên xuống trong quy hoạch động Với phương pháp này, sẽ bắt đầu giải bài toán từ trên xuống. Bằng cách lặp đệ quy để giải bài toán lớn hơn, từ đó tìm ra lời giải cho các bài toán con. Các bài toán con này được giải và lưu kết quả vào bộ nhớ. Việc ghi nhớ câu trả lời này sẽ giúp giải quyết vấn đề con mà không tốn quá nhiều thời gian. Phương pháp từ dưới lên ( phương pháp lập bảng ) Phương pháp từ dưới lên trong thuật toán quy hoạch động 5
Phương pháp lập bảng này trái ngược hoàn toàn với phương pháp ghi nhớ. Cách tiếp cận này sẽ không dùng đệ quy và giải quyết bài toán con liên quan từ dưới lên. Bạn trực tiếp giải tất cả bài toán nhỏ và điền vào bảng N chiều. Sau đó, dùng kết quả trong bảng để tìm ra dần lời giải cho bài toán ban đầu. Cách tiếp cận này hiệu quả và được sử dụng nhiều hơn phương pháp ghi nhớ bởi nó sẽ không làm tốn bộ nhớ và số lần gọi hàm. 1.2. Độ phức tạp của thuật toán Giả sử ta có hai thuật toán P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3). Khi n > 20 thì T1 < T2. Sở dĩ như vậy là do tỷ suất tăng của T1 nhỏ hơn tỷ suất tăng của T2. Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiện.Cho một hàm T(n), T(n) gọi là có độ phức tạp f(n) nếu tồn tại các hằng C, N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là “ô của f(n)”). Các hàm thể hiện độ phức tạp có các dạng thường gặp sau: log2n, n, nlog2n, n2, n3, 2n, n!, nn. Trong cách viết, ta thường dùng logn thay thế cho log2n cho gọn. Khi ta nói đến độ phức tạp của thuật toán là ta nói đến hiệu quả thời gian thực hiện chương trình nên có thể xem việc xác định thời gian thực hiện chương trình chính là xác định độ phức tạp của thuật toán. 1.3. Phương pháp lựa chọn và cài đặt chương trình tối ưu khi giải một số dạng bài tập về dãy con Đối với mỗi dạng bài tập về dãy con, chúng tôi đưa ra một bài toán cơ bản, từ mỗi bài toán cơ bản chúng tôi trình bày từ 2 hoặc 3 cách giải (cả cách làm của học sinh và cách làm chúng tôi định hướng cho học sinh làm). Với phương châm“ mưa dầm thấm lâu”, chúng tôi không hướng dẫn học sinh cách làm tối ưu ngay mà khi phát vấn một dạng bài tập mới mà yêu cầu học sinh làm theo các trình tự sau: Bước 1: Xác định bài toán Bước 2: Suy nghĩ tìm ra thuật toán, viết chương trình, tính độ phức tạp (Có thể nhiều cách). Bước 3: Trao đổi cách làm của mình với bạn để tìm cái hay cái dở. Bước 4: Sử dụng phần mềm Themis-chấm bài tự động để chấm cách làm của mình (với 10 bộ test hoặc nhiều hơn mà giáo viên đã xây dựng sẵn, mỗi bộ test cấu hình là 1 điểm, thời gian chạy không quá 1 giây). Bước 5: Nhận xét sự tối ưu của thuật toán. Bước 6: Giáo viên định hướng cách làm tối ưu hơn (nếu có). Bước 7: Sử dụng phần mềm Themis để chấm tất cả các cách đã viết chương trình. Bước 8: Dựa vào kết quả, lựa chọn chương trình có độ phức tạp nhỏ nhất, thời gian thực hiện mỗi test nhỏ nhất và chương trình ngắn gọn dễ hiểu nhất. Bước 9: Lập trình giải các bài tập tương tương với cách đã lựa chọn. 6
2. Cơ sở thực tiễn 2.1. Thực trạng học tập của học sinh a) Khảo sát thực trạng Chúng tôi đã tiến hành khảo sát tìm hiểu thực trạng học tập của học sinh. Cụ thể, chúng tôi đã phát phiếu điều tra cho HS ở nhiều lớp khác nhau để các em phát biểu những cảm nhận và nêu ý kiến, nguyện vọng của mình về việc học môn Tin học. Nội dung khảo sát như sau : Hãy trả lời câu hỏi dưới đây bằng cách đánh dấu x vào ô trống trong bảng có câu trả lời phù hợp với em. Nội dung Có Không Câu 1: Em có yêu thích môn Tin học không? Câu 2: Em có yêu thích môn Tin học lập trình không? Câu 3: Em có biết về quy hoạch động không? - Kết quả thu được như sau: Nội dung khảo sát TT Lớp Câu 1 Câu 2 Câu 3 Có Không Có Không Có Không 45/45 0/45 15/45 30/45 1/45 44/45 1 10D1 100% 0% 33.3% 66.7% 2.2% 97.8% 40/50 10/50 30/50 20/50 3/50 47/50 3 10A 80% 20% 60% 40% 6% 94% 35/38 3/38 25/38 13/38 4/38 34/38 6 11A 92.1% 7.9% 65.8% 34.2% 10.5% 89.5% 36/40 4/40 23/40 17/40 10/40 30/40 7 11T 90% 10% 57.5% 42.5% 25% 75% 34/42 8/42 22/42 20/42 5/42 37/42 8 12T 81% 19% 52.4% 47.6% 11.9% 88.1% 30/32 2/32 15/32 17/32 4/32 28/32 9 12A1 93.7% 6.3% 46.9% 53.1% 12.5% 87.5% b) Phân tích, đánh giá thực trạng Từ kết quả khảo sát đó, chúng tôi nhận thấy: Đa số học sinh đều yêu thích môn Tin học nhất là trong lĩnh vực ứng dụng như tìm hiểu Internet tham gia các trò chơi trí tuệ, hay tự mình làm ra các phần mềm nhỏ như các trò chơi ô chữ trong các giờ học, hay tạo ra những video hình ảnh có ích trong các môn học. Tuy nhiên trong các nội dung ở trường THPT thì phần lập trình là khó khăn nhất dẫn đến học sinh không có hứng thú, bài toán có sử dụng quy hoạch động là một bài toán khó thường xuất hiện trong các đề thi học sinh giỏi môn Tin học, nên rất ít các em HS biết và sử dụng. 7
2.2. Thực trạng dạy học và kiểm tra đánh giá của giáo viên a) Khảo sát thực trạng Chúng tôi đã tiến hành tìm hiểu thực trạng việc dạy học và kiểm tra đánh giá của giáo viên (gồm 6 giáo viên dạy Tin học tại trường THPT Lê Viết Thuật). b) Phân tích, đánh giá thực trạng Chúng tôi nhận thấy: - Việc dạy học của giáo viên đang hướng dẫn và sử dụng các bài toán, thuật toán cơ bản. (chủ yếu sử dụng sách giáo khoa và sách bài tập Tin học 11) - Việc kiểm tra đánh giá của giáo viên vẫn còn nặng theo chuẩn kiến thức kĩ năng. - Đối với những HS có học lực môn Tin khá, giỏi, GV chưa tổ chức bồi dưỡng tập trung hết được mà chỉ dành hướng dẫn 1 số ít HS có tham gia đội tuyển HSG. GV cũng chưa có 1 tài liệu cụ thể để dạy bồi dưỡng HSG mà chỉ tìm hiểu tham khảo để hướng dẫn HS. Việc sử dụng các tài liệu chuyên tin cũng gặp khó khăn với năng lực HS của trường. 2.3. Thực trạng về tài liệu tham khảo a) Khảo sát thực trạng: Để có được kết luận về thực trạng tài liệu tham khảo, chúng tôi đã tiến hành khảo sát các tài liệu tham khảo: 1. Sách giáo khoa và sách bài tập môn Tin học lớp 11 (NXB GD Việt Nam). b) Phân tích, đánh giá thực trạng: Từ kết quả khảo sát đó, chúng tôi có nhận xét như sau: - Các sách trên đề cập đến các thuật toán Sắp xếp, tìm kiếm không đề cập đến thuật toán về quy hoạch động. - Đối với môn Tin học sách tham khảo dùng cho học sinh trong phần lập trình không phong phú như các môn tự nhiên khác nên khó khăn trong việc giảng dạy và học nội dung này. - Các chương trình mà một số tài liệu đưa ra rất khó hiểu và phức tạp không phù hợp năng lực học sinh đại trà Trường THPT Lê Viết Thuật. Vì vậy việc nghiên cứu và áp dụng đề tài “Sử dụng Quy hoạch động để giải quyết một số bài toán trong bồi dưỡng học sinh giỏi môn Tin học” hi vọng sẽ trở thành nguồn tài liệu tham khảo hữu ích cho giáo viên và học sinh trong quá trình dạy và học. II. Sử dụng Quy hoạch động để giải quyết một số bài toán trong bồi dưỡng học sinh giỏi môn Tin học 1. Dạng bài tập chủ đề về đoạn con đạt giá trị tối ưu (tổng, độ dài đạt max, min) Bài 1: Đoạn con có Tổng lớn nhất 8
Cho dãy số nguyên a[1], a[2],..., a[n]. Tìm đoạn con có tổng lớn nhất của dãy số trên. Input: Gồm có hai dòng, dòng đầu là số nguyên dương n ≤ 1000000, dòng thứ hai chứa n số nguyên mô tả dãy số trên. Output: Đưa ra một dòng là kết quả bài toán. Ví dụ: Input Output 7 18 1 -2 7 -3 2 3 9 Thuật toán: - Gọi F[i] là tổng lớn nhất mà các đoạn con kết thúc ở vị trí i có thể nhận, thì khi xét đến vị trí i có hai khả năng xảy ra: + Khả năng 1: Đoạn con này chỉ gồm một phần tử duy nhất là a[i], lúc đó F[i] = a[i]. + Khả năng 2: Đoạn con này có nhiều hơn 1 phần tử, tức là nó được kế thừa từ dãy con kết thúc ở a[i – 1], vậy thì lúc này dãy con có tổng lớn nhất mà ta có thể thu được chính là dãy con có tổng lớn nhất kết thúc ở a[i – 1] sau đó ghép thêm a[i] vào, hay nói một cách khác F[i] = F[i-1] + a[i]. - Trong hai khả năng trên, ta sẽ lấy khả năng tốt hơn để gán cho F[i], hay F[i] = max(F[i-1] + a[i], a[i]). - Lúc này kết quả của ta chính là vị trí có F đạt giá trị max. - Độ phức tạp: O(N). Chương trình: #include usingnamespace std; int n; int a[1000005]; longlong F[1000005]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i =1; i > a[i]; } for(int i =1; i
Bài 2: Dãy con đan dấu Cho dãy số nguyên a[1], a[2],..., a[n]. Tìm dãy con đan dấu có giá lớn nhất của dãy số trên. Dãy con đan dấu được định nghĩa như sau: Giả sử ta chọn dãy con bắt đầu từ i và kết thúc tại j của dãy số trên, lúc đó giá trị của dãy đan dấu sẽ là a[i] – a[i + 1] + a[i + 2] - ... +(-) a[j]. Input: Gồm có hai dòng, dòng đầu là số nguyên dương n ≤ 1000000, dòng thứ hai chứa n số nguyên mô tả dãy số trên. Output: Đưa ra một dòng là kết quả bài toán. Ví dụ: Input Output 7 21 1 -2 7 -3 2 3 9 Thuật toán: - Gọi F[i][0] là dãy đan dấu có giá trị lớn nhất kết thúc tại i, và a[i] mang dấu + ở trước, còn F[i][1] là dãy đan dấu có giá trị lớn nhất kết thúc tại i, và a[i] mang dấu - ở trước. Lúc này, tương tự như bài 1, F[i][0] sẽ được tính dựa trên F[i – 1][1] nếu ta lấy dãy đan dấu nhiều hơn 1 phần tử, hoặc chỉ lấy a[i] nếu như ta lấy đúng 1 phần tử, còn F[i][1] sẽ luôn phải được tính dựa trên F[i-1][0], do a[i] khi đứng một mình không thể mang dấu - ở trước nó theo định nghĩa ở trên. - Lúc này kết quả của ta sẽ là max(F[i][0], F[i][1]) với mọi i từ 1 tới n. - Độ phức tạp: O(N). Chương trình: #include usingnamespace std; constlonglong INF =1e18; int n; int a[1000005]; longlong F[1000005][2]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i =1; i > a[i];} for(int i =0; i
for(int i =1; i a[i];} for(int i =1; i
F[i]=1; if(a[i]> a[i -1]) F[i]+= F[i -1];} int answer =0; for(int i =1; i a[i];} 12
for(int i =1; i
longlong F[1000005]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i =1; i > a[i];} for(int i =1; i
- Vì vậy ở đây ta phải làm nhanh hơn, bằng cách dùng kĩ thuật quy hoạch động để chuẩn bị trước mảng sum[i] là tổng của các phần tử từ 1 cho đến i, lúc này để lấy tổng các phần tử nằm trong đoạn [L, R] ta chỉ việc lấy sum[R] – sum[L-1], như vậy sau khi chuẩn bị xong ta có thể trả lời mỗi câu hỏi trong Q truy vấn rất nhanh với độ phức tạp chỉ là O(1). - Công thức để tính được mảng sum rất đơn giản, do tổng của các phần tử từ 1 đến i chính là tổng của các phần tử từ 1 đến i – 1 sau đó cộng thêm a[i] vào, vì thế sum[i] = sum[i – 1] + a[i]. - Độ phức tạp: O(N + Q). Chương trình: #include usingnamespace std; int n, Q, a[1000005]; longlong sum[1000005]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i =1; i > a[i];} sum[0]=0; for(int i =1; i > Q; for(int i =1; i > L >> R; cout
10 14 1 7 -2 8 -3 6 4 -10 5 9 24 2 36 6 10 Thuật toán: - Mấu chốt của bài toán này nằm ở việc làm sao ta có thể lấy được dãy con có tổng lớn nhất của một dãy đã cho, điều này rất đơn giản, ta chỉ việc lấy tất cả những số > 0 của dãy và dĩ nhiên dãy được tạo bởi các số đó luôn là dãy con có tổng lớn nhất của dãy ban đầu, và trường hợp đặc biệt khi mà dãy không có số nào >= 0, thì dãy con có tổng lớn nhất của nó sẽ là dãy rỗng, với tổng = 0. - Đến đây, bài toán trở về giống với bài 6, chỉ khác ở chỗ công thức quy hoạch động của ta sẽ thay đổi đôi chút, bởi vì ta sẽ không lấy các số < 0 vào mảng sum của mình. - Độ phức tạp: O(N + Q). Chương trình: #include usingnamespace std; int n, Q, a[1000005]; longlong sum[1000005]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i =1; i > a[i];} sum[0]=0; for(int i =1; i > Q; for(int i =1; i > L >> R; cout
- Dòng thứ hai gồm n ký tự Latinh in hoa mô tả xâu S. Output: In ra một dòng là số xâu con thỏa mãn. Ví dụ: Input Output 11 2 NAMTHUSONVU Thuật toán: - Nhận xét rằng mỗi chữ “THU” sẽ được tạo thành bởi các chứ cái ‘T’, ‘H’, ‘U’ trong đó ký tự ‘H’ đứng ở giữa, vì vậy nếu như với mọi ký tự ‘H’ ở trong xâu S, ta biết được số lượng chữ ‘T’ nằm ở bên trái nó và số lượng chữ ‘U’ nằm ở bên phải nó thì ta lấy hai số này nhân với nhau sẽ ra số lượng chữ “THU” có thể tạo thành mà chứa ký tự ‘H’ này, và nếu làm như vậy với tất cả các chữ ‘H’ xuất hiện trong xâu S thì ta sẽ có được kết quả cần tìm. - Để làm được như vậy, việc duyệt qua các ký tự ‘H’ trong xâu là việc làm đơn giản, tuy nhiên nó tốn của ta độ phức tạp là O(N), vì vậy muốn hoàn thành công việc trong thời gian cho phép, ta chỉ có thể tính trước số lượng chữ ‘T’ ở bên trái cũng như số lượng chữ ‘U’ nằm bên phải của một vị trí nào đó. - Để có thể tính trước được thì ta sẽ sử dụng quy hoạch động như sau: o Gọi leftT[i] là số lượng ký tự ‘T’ nằm bên trái vị trí i, lúc đó, số lượng chữ ‘T’ nằm bên trái ký tự i sẽ là số lượng chữ ‘T’ nằm bên trái ký tự i – 1, và cộng thêm một nếu như chính ký tự i – 1 = ‘T’, hay nói một cách khác leftT[i] = (leftT[i – 1] + (S[i – 1] == ‘T’)); o Tương tự như trên, gọi rightU[i] là số lượng ký tự ‘U’ nằm bên phải vị trí i, lúc đó ta có công thức rightU[i] = rightU[i + 1] + (a[i + 1] == ‘U’), và tất nhiên với công thức quy hoạch động như trên, để có thể tính được mảng rightU[i] thì ta sẽ phải thực hiện vòng for ngược từ n về 1 chứ không phải từ 1 tới n như cách tính mảng leftT. - Độ phức tạp: O(N). Chương trình: #include usingnamespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; string S; cin >> n >> S; S =' '+ S; vector leftT(n +2,0); for(int i =1; i =1; i--){ rightU[i]= rightU[i +1]+(S[i +1]=='U');} 17
longlong result =0; for(int i =2; i < n; i++){ if(S[i]=='H'){ result +=(1LL* leftT[i]* rightU[i]);}} cout n >> S; S =' '+ S; vector F(n +1,0); int ans =0; for(int i =1; i