SKKN Sử dụng quy hoạch động đề nâng cao năng lực giải quyết một số vấn đề về dãy con bằng ngôn ngữ lập trình C++

lt;<'\n';
 TruyVet(k);
}
int main()
{
 freopen("daycontang.inp","r", stdin);
 freopen("daycontang.out","w", stdout);
 cin>>n;
 for (int i=1; i>a[i];
 QHD();
 InKQ();
 return 0;
}
Từ bài tập 1.3 ta thay đổi tính chất các phần tử của dãy con ta có bài tập 1.4 như sau:
Bài tập 1.4: Cho một dãy A gồm N số nguyên {a1, a2,, aN}. Dãy con ai, ai+1,, aj(1≤i≤j≤N) là dãy được tạo từ các phần tử liên tiếp của dãy A bắt đầu từ phần tử i và kết thúc ở phần tử j.
Yêu cầu: Hãy tìm dãy con liên tiếp có số phần tử dương nhiều nhất.
Dữ liệu vào: File văn bản dayconduong.inp gồm:
          - Dòng đầu ghi giá trị N (2≤N≤10000).
          - Dòng sau gồm N số nguyên{a1, a2,, aN} (-106≤ai≤106) mỗi số cách nhau một dấu cách.
Dữ liệu ra: File văn bản dayconduong.out gồm
- Dòng đầu ghi độ dài dãy con có số lượng phần tử dương dài nhất
- Dòng tiếp theo ghi giá trị các phần tử dãy con.
(Chú ý: Nếu không có dãy con nào thỏa mãn thì ghi 0)
Ví dụ:
dayconduong.inp
dayconduong.out
9
1 3 1 -2 -5 0 1 17 12
3
1 3 1
Hướng dẫn thuật toán: Tương tự bài tập 1.3  áp dụng cách 3 chỉ thay:
- Khởi tạo: mảng L=0; 
- Công thức quy hoạch động:
 Nếu a[i]>0 thì 
{
Truoc[i]=-1;
L[i]=1;
Nếu (L[i]<L[i-1]+1) thì
	{ 
L[i]=L[i-1]+1;
Truoc[i]=i-1;
	}
	}
Code tham khảo:
#include 
#define N 10001
#define ll long long
using namespace std;
ll a[N], L[N], Truoc[N];
ll n;
void QHD()
{
 fill(L,L+N,0);
 for (int i=1; i<=n; i++)
 {
 if (a[i]>0)
 {
 Truoc[i]=-1;
 L[i]=1;
 if (L[i]<L[i-1]+1) {L[i]=L[i-1]+1; Truoc[i]=i-1;}
 }
 }
}
void TruyVet(ll i)
{
 if (Truoc[i]==-1) cout<<a[i];
 else
 {
 TruyVet(Truoc[i]);
 cout<<" "<<a[i];
 }
}
void InKQ()
{
 int MaxL=0, k=0;
 for (int i=1; i<=n; i++)
 {
 if (L[i]>MaxL) {MaxL=L[i]; k=i;}
 }
 cout<<MaxL<<'\n';
 TruyVet(k);
}
int main()
{
 freopen("dayconduong.inp","r", stdin);
 freopen("dayconduong.out","w", stdout);
 cin>>n;
 for (int i=1; i>a[i];
 QHD();
 InKQ();
 return 0;
}
Các dãy con có thể chung nhau phần tử của dãy ban đầu nghĩa là những phần tử của dãy mẹ đã thuộc dãy con thỏa mãn này thì vẫn có thể thuộc hoặc không thuộc các dãy con thỏa mãn khác.
Ví dụ: Dãy ban đầu gồm 7 phần tử {1,2,3,6,9,-6,8}. Dãy con {1,2,3}; {1,2,3,6}; {-6,8} là các dãy con có thể chung nhau phần tử của dãy ban đầu từ đó ta có bài tập 1.5 như sau:
Bài tập 1.5: Cho một dãy A gồm N số nguyên {a1, a2,, aN}. Dãy con ai, ai+1,, aj(1≤i≤j≤N) là dãy được tạo từ các phần tử liên tiếp của dãy A bắt đầu từ phần tử i và kết thúc ở phần tử j. Tìm các dãy con thõa mãn một điều kiện nào đó.
Để giải dạng bài tập này ta có thể sử dụng thuật toán vét cạn các dãy con hoặc sử dụng phương pháp quy hoạch động. Đối với dạng bài tập này chúng tôi định hướng cho học sinh lựa chọn thuật toán quy hoạch động.
Mô hình thuật toán:
- Gọi L[i] là giá trị dãy con (tùy điều kiện bài toán) từ phần tử thứ 1 đến phần tử thứ i
- Lập công thức tính giá trị dãy con từ i đến j theo L[i] và L[j].
- Xét tất cả các cặp số (i, j) bằng hai vòng lặp sau:
for (int i=1; i< n; i++)
{
            for (int j=i; j<=n; j++)
               {  
Xét các dãy con từ phần tử i đến j thỏa mãn điều kiện thì tăng số dãy, lưu chỉ số đầu, chỉ số cuối
 }
}
Bài tập 1.6: Cho một dãy A gồm N số nguyên {a1, a2, , aN}. Dãy con ai, ai+1, , aj(1 ≤ i ≤ j ≤ N) là dãy được tạo từ các phần tử liên tiếp của dãy A bắt đầu từ phần tử i và kết thúc ở phần tử j.
Yêu cầu: Hãy tìm dãy con liên tiếp có tổng lớn nhất.
Dữ liệu vào: File văn bản tonglt.inp gồm:
- Dòng đầu ghi giá trị N (1≤N≤10000).
- Dòng sau gồm N số nguyên{a1, a2, , aN} (-106 ≤ ai ≤ 106) mỗi số cách nhau một dấu cách.
Dữ liệu ra: File văn bản tonglt.out gồm
- Dòng đầu ghi tổng các phần tử dãy con và số lượng dãy con.
- Dòng tiếp theo ghi giá trị các phần tử dãy con.
Ví dụ:
Tonglt.inp
Tonglt.out
13
12 -34 14 11 9 -8 15 11 -7 -56 17 16 19
52  2
14 11 9 -8 15 11
17 16 19
 	Cách 1: Khi gặp bài toán này thông thường học sinh sẽ sử dụng phương pháp vét cạn các dãy con như sau:
Mô hình thuật toán:
Code tham khảo:
#include 
#define N 10001
#define ll long long
using namespace std;
ll a[N], dau[N], cuoi[N];
ll n;
ll tong(ll m, ll l)
{
 ll t=0;
 for (int i=m; i<=m+l-1; i++)
 t+=a[i];
 return t;
}
int main()
{
 freopen("tonglt.inp","r", stdin);
 freopen("tonglt.out","w", stdout);
 cin>>n;
 for (int i=1; i>a[i];
 ll tmax=a[1];
 int k=0;
 for (int i=1; i<=n-1; i++)
 for (int j=1; j<=n-i+1; j++)
 {
 ll t=tong(i,j);
 if (t>tmax) {tmax=t; k=0;}
 if (t==tmax) {k+=1;dau[k]=i; cuoi[k]=i+j-1;}
 }
 cout<<tmax<<" "<<k<<'\n';
 for (int i=1; i<=k; i++)
 {
 for (int j=dau[i]; j<=cuoi[i]; j++) cout<<a[j]<<" ";
 cout<<'\n';
 }
 return 0;
}
Sử dụng phần mềm Themis. Ta đo được thời gian thực hiện mỗi test cụ thể như sau:
Cách 1
Độ
phức
tạp
Test01 (giây)
Test02
(giây)
Test03
(giây)
Test04
(giây)
Test05
(giây)
Test06
(giây)
Test07
(giây)
Test08
(giây)
Test09
(giây)
Test10
(giây)
0(n2logn)
0.0745
0.3465
2.5423
53.666
>100
>100
>100
>100
>100
>100
Với cách này thì đạt được 20% số test. Vì một số test có dữ liệu lớn chạy quá thời gian.
Cách 2: Sử dụng phương pháp quy hoạch động.
Mô hình thuật toán:
- Gọi L[i] là tổng tất cả các phần tử từ 1 đến i.
- Như vậy dãy con liên tiếp từ i đến j có tổng là: L[j]-L[i-1].
- Xét tất cả các dãy con từ i đến j bằng 2 vòng lặp:
for i:= 1 to n-1 do
            for j:= i to n do
begin
{Xét L[j]-L[i-1] thỏa mãn điều kiện thì tăng số dãy, lưu chỉ số đầu, chỉ số cuối}
end;
 	Code tham khảo:
#include 
#define N 10001
#define ll long long
using namespace std;
ll a[N], L[N], dau[N], cuoi[N];
ll n;
int main()
{
 freopen("tonglt.inp","r", stdin);
 freopen("tonglt.out","w", stdout);
 cin>>n;
 for (int i=1; i>a[i];
 L[0]=0;
 for (int i=1; i<=n; i++) L[i]=L[i-1]+a[i];
 ll tmax=a[1];
 int k=0;
 for (int i=1; i<=n-1; i++)
 for (int j=i; j<=n; j++)
 {
 if (L[j]-L[i-1]>tmax) {tmax=L[j]-L[i-1]; k=0;}
 if (L[j]-L[i-1]==tmax) {k++; dau[k]=i; cuoi[k]=j;}
 }
 cout<<tmax<<" "<<k<<'\n';
 for (int i=1; i<=k; i++)
 {
 for (int j=dau[i]; j<=cuoi[i]; j++)
 cout<<a[j]<<" ";
 cout<<'\n';
 }
 return 0;
}
Sử dụng phần mềm Themis. Ta đo được thời gian thực hiện mỗi test cụ thể như sau:
Cách 2
Độ
phức
tạp
Test01 (giây)
Test02
(giây)
Test03
(giây)
Test04
(giây)
Test05
(giây)
Test06
(giây)
Test07
(giây)
Test08
(giây)
Test09
(giây)
Test10
(giây)
0(n2)
0.0556
0.0886
0.1123
0.1312
0.1764
0.2754
0.3352
0.3733
0.4373
0.5364
Với cách này thì đạt được 100% số Test. Do đó nên sử dụng cách thứ 2
So sánh kết quả từ 2 bảng trên và kết quả chấm điểm bài toán 1.6 bằng phần mềm Themis của 2 cách trên như sau (mỗi test đúng và thời gian chạy không quá 1 giây/ 1 test được 1 điểm). Dễ dàng nhận thấy cách 2 là tối ưu hơn mà chương trình ngắn gọn dễ cài đặt phù hợp với năng lực học sinh trường chúng tôi. Do vậy giải các bài tập dạng này ta nên lựa chọn cách 2.
Bài tập 1.7: Cho một dãy A gồm N số nguyên {a1, a2, , aN} và một số nguyên K. Dãy con ai, ai+1, , aj (1 ≤ i ≤ j ≤ N) là dãy được tạo từ các phần tử liên tiếp của dãy A bắt đầu từ phần tử i và kết thúc ở phần tử j.
Yêu cầu: Hãy tìm dãy con liên tiếp có tổng các phần tử chia hết cho K.
Dữ liệu vào: File văn bản dayconchiam.inp gồm:
          - Dòng đầu ghi hai số nguyên N và M (1 ≤ N ≤ 10000 ; 1 ≤ M ≤ 1000).
          - Dòng sau gồm N số nguyên{a1, a2, , aN} (106 ≤ ai ≤ 106, ai 0) mỗi số cách nhau một dấu cách.
Dữ liệu ra: File văn bản dayconchiam.out gồm
- Dòng đầu ghi số lượng dãy con thỏa mãn.
- Dòng tiếp theo ghi giá trị các phần tử dãy con thỏa mãn.
Ví dụ:
dayconchiak.inp
dayconchiak.out
4 3
1 3 2 5
2
1 3 2
3
Thuật toán:
Tương tự cách 2 bài tập 1.6 chỉ thay điều kiện bằng L[j]-L[i-1] mod k =0.
Code tham khảo:
{Sử dụng phương pháp quy hoạch động}
#include 
#define N 10001
#define ll long long
using namespace std;
ll a[N], L[N], dau[N], cuoi[N];
ll n, m;
int main()
{
 freopen("dayconchiak.inp","r", stdin);
 freopen("dayconchiak.out","w", stdout);
 cin>>n>>m;
 for (int i=1; i>a[i];
 L[0]=0;
 for (int i=1; i<=n; i++) L[i]=L[i-1]+a[i];
 ll tmax=a[1];
 int k=0;
 for (int i=1; i<=n-1; i++)
 for (int j=i; j<=n; j++)
 {
 if ((L[j]-L[i-1])% m == 0) {k++; dau[k]=i; cuoi[k]=j;}
 }
 cout<<k<<'\n';
 for (int i=1; i<=k; i++)
 {
 for (int j=dau[i]; j<=cuoi[i]; j++)
 cout<<a[j]<<" ";
 cout<<'\n';
 }
 return 0;
}
2.5 Các bài toán về dãy con không liên tiếp
Bài tập 2: (Bài toán cơ bản)
Cho một dãy A gồm N số nguyên {a1, a2,, aN}. Dãy con ai, ai+1,, aj(1≤i≤j≤N) là dãy thu được khi ta xóa một số phần tử (có thể không xóa phần tử nào và không được xóa hết) của một dãy cho trước và giữ nguyên thứ tự các phần tử còn lại trong dãy. Hãy tìm các dãy con thỏa mãn một điều kiện nào đó.
Đối với dạng bài tập này chúng tôi định hướng cho học sinh lựa chọn thuật toán quy hoạch động là tối ưu hơn cả.
Thuật toán chung
- Phân rã bài toán
- Gán giá trị cho bài toán cơ sở.
- Tính giá trị cho bài toán thứ i nhờ các bài toán đã tính trước đó.
- Kết quả bài toán là sự tổng hợp từ các bài toán ban đầu.
Bài tập 2.1: Dãy con không giảm
Cho một dãy A gồm N số nguyên {a1, a2,, aN}. Dãy con ai≤ai+1≤≤ aj(1≤i≤j≤N) được gọi là dãy con không giảm của dãy A. Lưu ý các phần tử của dãy con có thể chọn liên tiếp hoặc không liên tiếp từ các phần tử dãy A nhưng phải theo đúng thứ tự. Độ dài của dãy con là số lượng phần tử của dãy con đó.
Yêu cầu: Tìm độ dài lớn nhất của dãy con không giảm.
Dữ liệu vào: File văn bản dayconkogiam.inp gồm 2 dòng:
- Dòng đầu chứa một số nguyên dương N (1≤  N ≤ 104).
- Dòng thứ hai chứa N số nguyên dương ai ((-105≤ai ≤  105), giữa hai