Vận dụng phương pháp qui hoạch động vào giải các bài toán trong ôn thi học sinh giỏi môn Tin học

Nội dung text: Vận dụng phương pháp qui hoạch động vào giải các bài toán trong ôn thi học sinh giỏi môn Tin học

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO BẮC GIANG TRƯỜNG PHỔ THÔNG DÂN TỘC NỘI TRÚ TỈNH THUYẾT MINH MÔ TẢ GIẢI PHÁP VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN Vận dụng phương pháp qui hoạch động vào giải các bài toán trong ôn thi học sinh giỏi môn Tin học Họ và tên tác giả: Chu Thị Tú Anh Chuyên môn: Tin học Tổ: Tổng Hợp Chức vụ: Tổ trưởng chuyên môn Đơn vị công tác: Trường Phổ thông DTNT Tỉnh Bắc Giang, tháng 03 năm 2024 ***
2. MỤC LỤC 1. Tên sáng kiến:. ................................................................................................. 3 2. Ngày sáng kiến được áp dụng lần đầu .......................................................... 3 3. Các thông tin cần bảo mật. ............................................................................. 3 4. Mô tả giải pháp cũ thường làm ...................................................................... 3 5. Sự cần thiết phải áp dụng giải pháp sáng kiến ............................................. 3 6. Mục đích của giải pháp sáng kiến .................................................................. 3 7. Nội dung ........................................................................................................... 4 7.1 Thuyết minh giải pháp mới hoặc cải tiến .................................................... 4 7.1.1 Cơ sở lý thuyết ............................................................................................ 4 7.1.1.1 Khái niệm qui hoạch động .................................................................. 4 7.1.1.2 Khi nào thì dùng thuật toán quy hoạch động ...................................... 4 7.1.1.3 Phương pháp chung . 5 7.1.2 Các bài toán áp dụng ..5 7.1.2.1 Xâu con đối xứng dài nhất .................................................................. 5 7.1.2.2 Bài Phần thưởng .................................................................................. 9 7.1.2.3 Bài Tặng quà ..................................................................................... 13 7.1.2.4 Bài toán Con Ếch .............................................................................. 18 7.1.2.5 Bài Đường đi ..................................................................................... 20 7.1.2.6 Bài Nhảy trên các bậc thang.............................................................. 22 7.1.2.7 Bái toán ValiA ................................................................................... 23 7.1.2.8 Bài toán cây khế ................................................................................ 25 7.1.2.9 Bài toán Chia kẹo .............................................................................. 27 7.1.2.10 Bài toán Bố trí phòng họp ............................................................... 30 7.1.2.11 Một số bài toán khác ....................................................................... 33 7.2 Phạm vi áp dụng sáng kiến ......................................................................... 39 7.3 Lợi ích kinh tế, xã hội của sáng kiến ........................................................ 39 8. Tài liệu tham khảo......................................................................................... 40
3. 3 CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập- Tự do- Hạnh phúc THUYẾT MINH MÔ TẢ GIẢI PHÁP VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN 1. Tên sáng kiến: “Vận dụng phương pháp qui hoạch động vào giải các bài toán trong ôn thi học sinh giỏi môn Tin học”. 2. Ngày sáng kiến được áp dụng lần đầu: ngày 1/3/2023. 3. Các thông tin cần bảo mật: không có. 4. Mô tả giải pháp cũ thường làm Trong các kì thi học sinh giỏi môn Tin học hay Tin học trẻ, các bài toán vận dụng phương pháp qui hoạch động để giải quyết là một dạng bài toán trong đề thi học sinh giỏi môn Tin học. Đây là một dạng bài toán khó đối với các em học sinh THPT, khi gặp các bài toán này các em chưa xác định được dạng bài toán nên thường sử dụng các thuật toán đơn giản, dễ cài đặt tuy nhiên có độ phức tạp lớn, thường chỉ được ít điểm với một số bộ test có dữ liệu nhỏ. Với các bộ test lớn các em học sinh sử dụng thuật toán như vậy thì chương trình sẽ bị mất điểm (do chạy quá thời gian qui định đối với các bộ test lớn hoặc tràn bộ nhớ), không đạt được số điểm tuyệt đối của bài. Vậy làm thế nào để chương trình chạy đúng mà đảm bảo thời gian chạy chương trình theo qui định cho mỗi bộ test? Làm thế nào để lấy được điểm tuyệt đối với các bộ test có dữ liệu lớn? 5. Sự cần thiết phải áp dụng giải pháp sáng kiến Qua việc áp dụng sáng kiến vào giảng dạy trong thực tế, giúp học sinh khá, giỏi rèn luyện kỹ năng lập trình, khơi dậy niềm say mê, yêu thích đối với bộ môn Tin học. Với những dạng bài toán sử dụng phương pháp qui hoạch động, học sinh xác định được dạng bài toán và dựa vào cấu trúc dữ liệu biết lựa chọn thuật toán phù hợp để giải quyết bài toán một cách tối ưu, từ đó giúp học sinh đạt điểm tối đa trong các bài thi. 6. Mục đích của giải pháp sáng kiến Với mục đích giải quyết các bài toán một cách tối ưu vận dụng phương pháp qui hoạch động, trong sáng kiến này tôi trình bày phương pháp giải bài
4. 4 toán thông qua các ví dụ cụ thể, từ đó khi gặp một bài toán dạng tương tự học sinh có thể phân tích bài toán, nhận biết bài bài toán có thể vận dụng phương pháp qui hoạch động để giải quyết, biết dựa vào cấu trúc dữ liệu bài toán để lựa chọn thuật toán tối ưu, xây dựng trường hợp cơ sở và công thức truy hồi cho bài toán (thuật toán tối ưu là thuật toán sử dụng ít thời gian, tiết kiệm bộ nhớ, ít phép toán), để khi chạy chương trình với các bộ test lớn cho kết quả chính xác và thời gian chạy không quá thời gian qui định. 7. Nội dung 7.1 Thuyết minh giải pháp mới hoặc cải tiến 7.1.1 Cơ sở lý thuyết 7.1.1.1 Khái niệm qui hoạch động Quy hoạch động (Dynamic Programming) là một phương pháp tối ưu trong đó bài toán lớn được phân chia thành các bài toán đơn giản hơn. Sau đó, từ kết quả của bài toán đơn giản hơn, ta sẽ tính được kết quả của bài toán ban đầu. 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 đó. 7.1.1.2 Khi nào thì dùng thuật toán quy hoạch động Với những bài toán có tính chất nổi bật dưới đây thì chúng ta có thể nghĩ đến bài toán qui hoạch động: Thứ nhất: Bài toán có các bài toán con gối nhau. Thứ hai: Bài toán có cấu trúc con tối ưu. 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. Ví dụ bài toán dãy số Fibonacci: Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng 1 và 1, sau đó các số tiếp theo sẽ bằng tổng của 2 số liền trước nó: Cho f(1)=f(2)=1; f(n)=f(n-1)+f(n-2) (n>2). Bằng cách cộng số 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 là bài toán tính số Fibonacci n-1 và n-2.
5. 5 Quy hoạch động chính là một trong số những giải pháp cực kỳ hiệu quả có thể tối ưu hóa quá trình tính toán này. Trước khi tiến hành tính những bài lớn thì mỗi bài toán con sẽ được lưu lại. Nhờ đó, mà việc tính toán giảm đi đáng kể, mỗi bài toán con chỉ cần tính đúng một lần. Nhờ đó mà thuật toán này được sử dụng rất nhiều trong các cuộc thi lập trình giúp các thí sinh giảm đáng kể thời gian tính toán. Cấu trúc con tối ưu Bài toán có cấu trúc con tối ưu là gì? Cấu trúc con tối ưu chính là tập hợp các lời giải tối ưu từ các bài toán con để tìm ra lời giải bài toán lớn. Bài toán có cấu trúc 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. 7.1.1.3 Phương pháp chung Để có thể giải được một bài toán quy hoạch động, chúng ta sẽ cần hai yếu tố cơ bản nhất đó là công thức truy hồi và trường hợp cơ sở. Ví dụ với bài toán về số Fibonacci, ta đã biết công thức truy hồi là: f(n)=f(n-1)+f(n-2). Bản chất của công thức này là đệ quy. Vậy thì nó sẽ đệ quy đến khi nào? Ta cũng biết là f(1)=f(2)=1 nên khi n=1 hoặc n=2 thì ta lấy luôn kết quả f(n)=1, đây chính là trường hợp cơ sở. Như vậy, lời giải quy hoạch động của bài toán tìm số Fibonacci thứ n có thể biểu diễn như sau: f(n)=f(n-1)+f(n-2) với n>2 và f(1)=f(2)=1 Với những bài toán phức tạp thì công thức truy hồi sẽ không chỉ đơn giản là một công thức mà có thể là nhiều hàm, nhiều biến cùng được tính để cho ra kết quả. 7.1.2 Các bài toán áp dụng 7.1.2.1 Xâu con đối xứng dài nhất (Đề thi HSG cấp tỉnh năm 2018- 2019) Cho xâu ký tự S, ta có thể lấy ra từ S các ký tự để tạo ra xâu con của nó. Nếu ta lấy ra các ký tự liên tiếp nhau thì ta được xâu con các ký tự liên tiếp. Ta cũng có thể lấy ra lần lượt các ký tự từ đầu xâu về cuối xâu ở vị trí bất kỳ và ghép chúng lại thành xâu theo thứ tự ấy, lúc đó ta được xâu con các ký tự ở vị trí
6. 6 bất kỳ. Độ dài của xâu con cũng chính là số lượng ký tự trong xâu con. Một xâu là đối xứng nếu đọc nó từ phải sang trái cũng thu được kết quả giống như đọc từ trái sang phải. Ví dụ: cho xâu S là „thi hsg tin hoc cap tinh‟, ta có xâu „hsg tin hoc‟ là một xâu con các ký tự liên tiếp, còn „thi tin hoc‟ là một xâu con các ký tự ở vị trí bất kỳ. Xâu „xaxa‟ không phải là xâu đối xứng, xâu „xaax‟ là xâu đối xứng có độ dài là 4. Yêu cầu: Cho xâu S, hãy tìm xâu con đối xứng dài nhất? Dữ liệu: vào từ tệp văn bản SUBSTR.INP ghi xâu S. Kết quả: ghi ra tệp văn bản SUBSTR.OUT gồm: Dòng 1: ghi độ dài của xâu con đối xứng dài nhất gồm các ký tự liên tiếp; Dòng 2: ghi độ dài của xâu con đối xứng dài nhất gồm các ký tự ở vị trí bất kỳ. Ví dụ: SUBSTR.INP SUBSTR.OUT Giải thích xaxaax 4 - Xâu con các ký tự liên tiếp đối xứng 5 dài nhất: xaax (xaxaax) - Xâu con các ký tự ở vị trí bất kỳ đối xứng dài nhất: xaxax (xaxaax, xaxaax) hoặc xaaax (xaxaax) Giới hạn: Có 10/15 test có độ dài của xâu ≤ 200, tương ứng 2,0 điểm; Có 5/15 test có 200 < độ dài của xâu ≤1000, tương ứng 1,0 điểm. Giải thuật: - Tạo xâu P là xâu đảo ngược của xâu S ban đầu - Xâu con chung của P và S chính là một xâu con đối xứng của S. - Tìm xâu con chung độ dài lớn nhất của P và S. Gọi F[i,j] là số độ dài lớn nhất của xâu con chung gồm các ký tự P[1], P[2], .., P[i] và S[1], S[2], .., S[N] khi đó: Trường hợp cơ sở: F[0,j] =0; F[i,0] = 0; Công thức truy hồi: Nếu P[i]=P[j] thì F[i,j] = F[i-1,j-1] +1 Nếu P[i] ≠ P[j] thì F[i,j] = max(F[i-1, j], F[i,j-1]
7. 7 Code C++ #include using namespace std; typedef long long ll; typedef pair ii; typedef unsigned long long ull; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll Rd(ll l,ll r) { return uniform_int_distribution (l,r)(rng); } #define X first #define Y second #define pb push_back #define mp make_pair #define ep emplace_back #define EL printf("\n") #define sz(A) (int) A.size() #define FOR(i,l,r) for (int i=l;i<=r;i++) #define FOD(i,r,l) for (int i=r;i>=l;i--) #define fillchar(a,x) memset(a, x, sizeof (a)) #define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); const int maxn=1e6+7; const int base=31; const ll Mod=1000000007; int n; string S,T; ll hS[maxn],pS[maxn],hT[maxn],pT[maxn]; ll f[1005][1005]; ll gethS(ll l,ll r){
8. 8 return (hS[r]-hS[l-1]*pS[r-l+1] + Mod*Mod)%Mod; } ll gethT(ll l,ll r){ return (hT[r]-hT[l-1]*pT[r-l+1] + Mod*Mod)%Mod; } int main() { freopen("SUBSTR.INP","r",stdin); freopen("SUBSTR.OUT","w",stdout); getline(cin,S); n=S.length(); T=S; reverse(T.begin(),T.end()); S=" "+S; T=" "+T; pS[0]=pT[0]=1; hS[0]=hT[0]=1; FOR(i,1,n) { hS[i]=(hS[i-1]*base + S[i]-'a'+1)%Mod; hT[i]=(hT[i-1]*base + T[i]-'a'+1)%Mod; pS[i]=(pS[i-1]*base)%Mod; pT[i]=(pT[i-1]*base)%Mod; } ll res1=0; FOR(i,1,n){ FOR(j,i,n){ if(gethS(i,j)==gethT(n-j+1,n-i+1)) res1=max(res1,j- i+1*1ll); } } FOR(i,1,n){ FOR(j,1,n){
9. 9 if(S[i]==T[j]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } } cout << res1 << '\n' << f[n][n]; } 7.1.2.2 Bài Phần thưởng (Đề thi HSG cấp tỉnh năm học 2019- 2020) Trong cuộc thi lập trình APOLO do công ty GRIS tổ chức, Tuấn đạt được danh hiệu “Coder xuất sắc”. Nhà tài trợ Bin Gate cho phép Tuấn được tự lựa chọn phần thưởng cho mình. Trên khán đài xếp một dãy 푛 hộp quà được đánh số thứ tự từ 1 đến n, mặt trước của hộp quà i ghi một số nguyên dương ai tương ứng với giá trị của món quà chứa trong nó, nghĩa là ai càng lớn thì món quà càng có giá trị cao. Tuấn được phép chọn các hộp quà tuỳ ý trong n hộp quà, tuy nhiên Tuấn không được phép chọn hộp quà liền nhau, đó là thử thách nhỏ của nhà tài trợ. 6 10 10 13 10 10 1 2 3 4 5 6 Yêu cầu: Bạn hãy cho biết Tuấn có thể chọn những hộp quà nào để tổng giá trị của các hộp quà mà Tuấn chọn là lớn nhất?. Dữ liệu: Vào từ file văn bản BONUS.INP Dòng 1 chứa hai số nguyên n và k (1≤ 푛 ≤ 106;2 ≤ ≤ 106); Dòng 2 chứa n số nguyên dương a1, a2, , an tương ứng là giá trị của n hộp quà của nhà tài trợ theo thứ tự liệt kê từ hộp quà thứ nhất tới hộp quà thứ 푛. Kết quả: Ghi ra file văn bản BONUS.OUT một số duy nhất là tổng giá trị lớn nhất của các hộp quà mà Tuấn có thể nhận được. Ví dụ: BONUS.INP BONUS.OUT 6 3 40 6 10 10 13 10 10
10. 10 Lưu ý: Các số nằm trên cùng một dòng trong các tệp dữ liệu vào được đặt cách nhau dấu cách. Giới hạn: Có 20/40 test với 1 < n, k < 1000, tương ứng 1,5 điểm; Có 20/40 test với 1000 < n, k < 106 , tương ứng 1,5 điểm; Giải thuật: * sub1 (1 < n, k <= 1000): độ phức tạp O(n*n) Gọi L[i] là tổng tiền tố của mảng a trong đoạn [1..n] Gọi f[i] là tổng giá trị lớn nhất của các hộp quà mà Tuấn chọn, p[i] là tổng giá trị của các hộp quà mà Tuấn không chọn khi xét đến i. Trường hợp cơ sở: - Nếu i<k thì: f[i]=L[i] (Do số hộp chọn < k) p[i]= L[i]-f[i-1]: tổng giá trị của các hộp quà tuấn không chọn trong đoạn [1,i]. Công thức truy hồi: - nếu i >= k: duyệt i = k -> n : p[i] = L[i]-f[i-1]: tổng giá trị của các hộp quà tuấn không chọn trong đoạn [1,i]. Gọi t là giá trị nhỏ nhất của các hộp quà mà Tuấn không chọn trong đoạn [i-k+1...i].=> f[i] = max(f[i],L[i]-t)=> đáp án bài toán là f[n]. * sub2 (1000 < n, k <= 1000000): độ phức tạp O(nlogn) Cải tiến bài toán bằng cách sử dụng cấu trúc dữ liệu deque để áp dụng kĩ thuật tìm min, max trên đoạn tịnh tiến để tìm giá trị nhỏ nhất của các hộp quà mà Tuấn không chọn trong đoạn [i-k+1..i] ( i=k -> n) . => f[i]= max(f[i],L[i]-t); (t là giá trị nhỏ nhất [i-k+1....i]). => kết quả bài toán là f[n]. Code C++ #include using namespace std; typedef long long ll; typedef pair ii; typedef unsigned long long ull;
11. 11 mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll Rd(ll l,ll r) { return uniform_int_distribution (l,r)(rng); } #define X first #define Y second #define pb push_back #define mp make_pair #define ep emplace_back #define EL printf("\n") #define sz(A) (int) A.size() #define FOR(i,l,r) for (int i=l;i<=r;i++) #define FOD(i,r,l) for (int i=r;i>=l;i--) #define fillchar(a,x) memset(a, x, sizeof (a)) #define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); const int maxn=1e6+7; int n,k; ll a[maxn]; namespace Sub1{ ll L[maxn]; ll f[maxn]; ll p[maxn]; ll Main(){ L[0]=0; FOR(i,1,n) L[i]=L[i-1]+a[i]; FOR(i,1,k-1){ f[i]=L[i]; p[i]=L[i]-f[i-1]; } FOR(i,k,n){
12. 12 ll t=LLONG_MAX; p[i]=L[i]-f[i-1]; FOR(j,i-k+1,i){ t=min(t,p[j]); } f[i]=max(f[i],L[i]-t); } return f[n]; } } namespace Sub2{ ll L[maxn]; ll f[maxn]; ll p[maxn]; deque d; ll Main(){ L[1]=0; FOR(i,1,n) L[i]=L[i-1]+a[i]; FOR(i,1,k-1){ f[i]=L[i]; p[i]=L[i]-f[i-1]; while(!d.empty()&&p[d.back()]>=p[i])d.pop_back(); d.pb(i); } FOR(i,k,n){ p[i]=L[i]-f[i-1]; while(!d.empty() && p[d.back()]>=p[i]) d.pop_back(); while(!d.empty()&& d.front()<i-k+1) d.pop_front(); d.pb(i); f[i]=max(f[i],L[i]-p[d.front()]); } return f[n];
13. 13 } } int main() { freopen("BONUS.INP","r",stdin); freopen("BONUS.OUT","w",stdout); IOS ; cin >> n ; cin >> k ; FOR(i,1,n){ cin >> a[i]; } //ll x1=Sub1::Main(); ll x2=Sub2::Main(); cout << x2; } 7.1.2.3 Bài Tặng quà (Đề thi HSG cấp tỉnh năm học 2022- 2023) Trong kỳ thi chọn học sinh giỏi cấp tỉnh năm học 2022 – 2023. Để động viên, khích lệ tinh thần cho học sinh ban tổ chức có chương trình tặng quà cho tất cả học sinh tham dự kỳ thi. Ban tổ chức chuẩn bị sẵn n hộp đựng quà, mỗi hộp được đặt trên một bàn, các bàn đánh số từ 1 đến n. Trên hộp quà thứ i (i=1..n) có dán nhãn là ai và trong đó có món quà trị giá wi. Học sinh có thể chọn một hay nhiều hộp quà liên tiếp hay không liên tiếp từ hộp quà ở bàn 1 đến bàn n, hộp quà chọn sau phải có nhãn lớn hơn nhãn trên hộp quà chọn trước, tức là: { Em hãy chọn cho mình các món quà để có tổng trị giá là lớn nhất. * Dữ liệu vào: Đọc vào từ file văn bản QUA.INP gồm: - Dòng 1 ghi số nguyên dương n (n 5.105);
14. 14 9 - n dòng tiếp theo, dòng thứ i (i=1..n) ghi 2 số nguyên dương ai (ai 10 ) 6 và wi (wi 10 ) là nhãn và trị giá của món quà trong hộp i. Các số trên cùng dòng cách nhau ít nhất một khoảng trống. * Kết quả ra: Ghi ra file văn bản QUA.OUT một số duy nhất là tổng trị giá các món quà được chọn. * Ví dụ: QUA.INP QUA.OUT Giải thích QUA.INP QUA.OUT Giải thích 5 15 Chọn hộp 5 25 Có thể chọn các 5 15 quà thứ 1 4 10 hộp quà thứ 1, 3 3 5 có trị giá 1 3 có tổng trị giá là: 4 7 bằng 15 5 15 10+15=25 5 1 3 10 hoặc chọn các 2 8 4 12 hộp quà thứ 2, 4, 5 có tổng trị giá là: 3+10+12=25 * Giới hạn: - Có 10/30 test, tương ứng 1,0 điểm với n ≤ 103; - Có 20/30 test, tương ứng 2,0 điểm với 103 < n ≤ 5.105. Giải thuật: * Sub1: với n 103 - Tìm dãy con tăng, với mỗi dãy con tăng tính tổng các trị giá wi; - Gọi F[i] = tổng trọng số lớn nhất của dãy con tăng của dãy a[1..i], kết thúc ở phần tử a[i] - Trường hợp cơ sở: F[0]=0; - Công thức truy hồi: Để tính F[i] với i=1, 2, , n ta có nhận xét sau: + Để khi thêm phần tử a[i] vẫn tạo thành dãy con tăng thì a[i] phải nối vào sau phần tử a[j] (với j<i) thỏa mãn điều kiện a[j] < a[i] + Để F[i] lớn nhất thì trong số các chỉ số j thỏa mãn thì ta chọn vị trí j để F[j] lớn nhất Do đó: F[i] = max{F[j]| j<i và a[j] < a[i]} + w[i] - Cập nhật tổng trị giá của dãy con tăng lớn nhất; * Sub2: với n 5. 105 - Sử dụng cấu trúc dữ liệu cây Segment Tree để cài đặt thay cho mảng
15. 15 Code C++ #include using namespace std; typedef long long ll; typedef pair ii; typedef unsigned long long ull; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll Rd(ll l,ll r) { return uniform_int_distribution (l,r)(rng); } #define X first #define Y second #define pb push_back #define mp make_pair #define ep emplace_back #define EL printf("\n") #define sz(A) (int) A.size() #define FOR(i,l,r) for (int i=l;i<=r;i++) #define FOD(i,r,l) for (int i=r;i>=l;i--) #define fillchar(a,x) memset(a, x, sizeof (a)) #define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); const int maxn=1e6+7; int n ; ll a[maxn]; ll w[maxn]; namespace Sub1{ ll f[maxn]; ll Main(){ ll res=0; FOR(i,1,n){
16. 16 f[i]=w[i]; FOR(j,1,i-1){ if(a[j]<a[i]){ f[i]=max(f[i],f[j]+w[i]); } } res=max(res,f[i]); } return res; } } namespace Sub2{ struct Data{ ll gt,cs,W,nen; }; bool cmp1(Data &a,Data &b) { return a.gt < b.gt;} bool cmp2(Data &a,Data &b) { return a.cs < b.cs;} Data A[maxn]; ll ST[4*maxn]; ll f[maxn]; ll res=0; void update(ll id,ll l,ll r,ll pos,ll x){ if(pos > r || pos < l) return ; if(l==r){ ST[id]=max(ST[id],x); return ; } update(2*id,l,(l+r)>>1,pos,x); update(2*id+1,((l+r)>>1) + 1,r,pos,x); ST[id]=max(ST[2*id],ST[2*id+1]); }
17. 17 ll Get(ll id,ll l,ll r,ll u,ll v){ if(l>v || r<u) return 0; if(l>=u && r<=v){ return ST[id]; } return max(Get(2*id,l,((l+r)>>1),u,v),Get(2*id+1,((l+r)>>1) + 1,r,u,v)); } ll Main(){ FOR(i,1,n){ A[i].gt=a[i]; A[i].W=w[i]; A[i].cs=i; } sort(A+1,A+1+n,cmp1); int d=1; A[1].nen=1; FOR(i,2,n){ if(A[i].gt!=A[i-1].gt) ++d; A[i].nen=d; } sort(A+1,A+1+n,cmp2); FOR(i,1,n){ ll p=Get(1,1,n,1,A[i].nen-1); f[i] = p + A[i].W; update(1,1,n,A[i].nen,f[i]); res=max(res,f[i]); } return res; } } int main() {
18. 18 freopen("QUA.INP","r",stdin); freopen("QUA.OUT","w",stdout); IOS ; int t=1; while(t<=1) { cin >> n ; FOR(i,1,n) cin >> a[i] >> w[i]; //ll x1=Sub1::Main(); ll x2=Sub2::Main(); cout << x2; ++t; } } 7.1.2.4 Bài toán Con Ếch Cho n viên đá, viên đá thứ i có độ cao là hi. Con ếch đang đứng tại viên đá thứ nhất. Tại vị trí thứ i con ếch có thể nhảy sang hòn đá thứ i + 1 hoặc hòn đá thứ i + 2 với chi phí nhảy là |hi - hj| với j là vị trí đáp của chú ếch. Hãy tìm chi phí ngắn nhất để chú ếch tới được hòn đá thứ n. Input: -Dòng đầu gồm n là số lượng hòn đá (1 ≤ n ≤ 105) -Dòng sau gồm n số, số thứ i thể hiện hi là chiều cao của viên đá 4 thứ i (1 ≤ hi ≤ 10 ) Output: -Gồm một dòng duy nhất là đáp án cần tìm Giải thuật: Gọi f[i] là chi phí nhỏ nhất để ếch đến hòn đá thứ n , Ta có : Trường hợp cơ sở: f[0] = f[1] = 0 (Do ếch có vị trí ban đầu ở vị trí 1) f[2] = abs(a[2]-a[1]) (chi phí để ếch nhảy đến hòn đá thứ 2) Công thức truy hồi: Do ếch có thể nhảy từ hòn i đến hòn i+1,i+2 nên => ta có công thức quy hoạch động sau :
19. 19 f[i] = min(f[i-1] +abs(a[i-1]-a[i]) , f[i-2] + abs(a[i-2]-a[i])) ( với i=3->n) => kết quả bài toán trên là f[n]. Code C++ #include using namespace std; typedef long long ll; typedef pair ii; typedef unsigned long long ull; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll Rd(ll l,ll r) { return uniform_int_distribution (l,r)(rng); } #define X first #define Y second #define pb push_back #define mp make_pair #define ep emplace_back #define EL printf("\n") #define sz(A) (int) A.size() #define FOR(i,l,r) for (int i=l;i<=r;i++) #define FOD(i,r,l) for (int i=r;i>=l;i--) #define fillchar(a,x) memset(a, x, sizeof (a)) #define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); const int maxn=1e6+7; int n; ll h[maxn]; ll f[maxn]; int main() { IOS ;
20. 20 cin >> n; FOR(i,1,n) cin >> h[i]; f[0]=0; f[1]=0; f[2]=abs(h[1]-h[2]); FOR(i,3,n) { f[i]=min(f[i-1]+abs(h[i-1]-h[i]),f[i-2]+abs(h[i]-h[i-2])); } cout << f[n]; } 7.1.2.5 Bài Đường đi Một cô bé được mẹ giao nhiệm vụ đến thăm bà nội. Từ nhà mình đến nhà bà nội cô bé phải đi qua một khu rừng. Khu rừng được chia thành lưới ô vuông gồm n hàng và n cột. Nhà cô bé ở ô vuông đầu tiên trên cùng (1,1), nhà bà nội ở ô vuông dưới cùng (n,n) như hình vẽ. Cô bé chỉ được đi sang phải hoặc xuống dưới trong lưới hình vuông. (1,1) (n,n) Yêu cầu: Tìm số đường đi khác nhau từ nhà cô bé tới nhà bà nội. Dữ liệu: Vào từ tệp văn bản DUONGDI.INP ghi một số nguyên dương n (n ≤ 1000). Kết quả: Ghi ra tệp văn bản DUONGDI.OUT một số duy nhất là số đường đi tìm được. Ví dụ: DUONGDI.INP DUONGDI.OUT 4 20 Giới hạn: