SKKN Sử dụng phương pháp quy hoạch động để giải một số bài toán có tính truy hồi trong ngôn ngữ lập trình C++

ải bằng phƣơng pháp quy hoạch động:
Công thức:
+ Xây dựng hàm mục tiêu: L[i] là độ dài của đoạn con liên tiếp không giảm kết thúc tại a[i].
Độ dài đoạn con liên tiếp không giảm dài nhất là: max(L[])
+ Bài toán cơ sở: L[1] =1;
+ Xét a[i] (2≤i≤n):
Nếu a[i-1] ≤ a[i] thì L[i] = L[i-1] +1 (độ dài đoạn con liên tiếp không giảm sẽ nối thêm 1 đơn vị)
Nếu a[i-1] >a[i] thì L[i] =1; (phần tử đầu cho dãy không giảm mới)
#include #define N 10001
int a[N], f[N]; int n, res=0;
using namespace std; int main()
{
freopen("cau1.inp", "r", stdin);
freopen("cau1.out", "w", stdout);
Cài đặt chƣơng trình:
cin>>n;
for(int i=1; i>a[i];
L[1]=1;
for(int i=2; i<=n; i++)
{
if(a[i] >= a[i-1])
L[i] =L[i-1] +1;
else L[i]=1;
res= max(res, L[i]);
}
cout<<res; return 0;
}
Dạng bài toán về dãy con không liên tiếp:
 Mô hình: Bài toán điển hình: Cho dãy a1,a2,..an (1 <= n <= 103).
Yêu cầu: Hãy lập trình tìm dãy con tăng dài nhất trong dãy a. Dữ liệu vào: Đọc từ file DAYCON2.INP:
Dòng đầu tiên nhập số N
Dòng tiếp theo nhập các số A1, A2, , AN Dữ liệu ra: Ghi vào file DAYCON2.OUT
Dòng 1: một số nguyên dƣơng duy nhất là độ dài của dãy con dài nhất tìm đƣợc.
Dòng 2: Đƣa ra dãy con dài nhất tìm đƣợc
Ví dụ
daycon2.inp
daycon2.out
10
7 4 5 8 6 7 10 9 11 8
6
4 5 6 7 10	11

Cách 1:
 Công thức:
Phân rã bài toán:
Ta bổ sung 2 phần tử “lính canh” là a[0]= -∞ vào đầu dãy và a[n+1] = +∞ vào cuối dãy. Khi đó dãy con đơn điệu tăng dài nhất chắc chắn sẽ bắt đầu từ a[0] và kết thúc tại a[n]+1.
→ Tổng quát: Cần tìm độ dài của dãy con tăng dài nhất từ a[i] →a[n+1]
Xây dựng hàm mục tiêu:
Gọi L[i] là độ dài của dãy con tăng dài nhất bắt đầu tại a[i] với (0≤i≤n+1)
Suy ra kết quả của bài toán là: L[n+1] - 2
Bài toán cơ sở: Ta dễ dàng thấy đƣợc L[n+1] =1; (Dãy con bắt đầu từ a[n+1] = -∞, dãy con này gồm 1 phần tử là -∞ nên L[n+1]=1.
Xây dựng công thức:
Xét a[i]:
Nếu a[i] <a[j] (với 0≤i<j) thì L[i] = L[jmax] +1)
Dãy con đơn điệu tăng dài nhất bắt đầu từ a[i] sẽ đƣợc thành lập bằng cách lấy a[i] ghép vào đầu một trong những dãy con đơn điệu tăng dài nhất bắt đầu tại a[j] mà a[i] < a[j] (i+1≤j≤n+1).
Vậy L[i] sẽ đƣợc tính: Xét tất cả các chỉ số j trong khoảng từ i+1 đến n+1 mà a[j] > a[i], chọn ra chỉ số jmax có L[jmax] lớn nhất.
Truy vết:
Tại bƣớc xây dựng L, mỗi khi tính L[i] =L[jmax]+1, ta đặt T[i]=jmax, để lƣu lại dãy con tăng dài nhất bắt đầu tại a[i] sẽ có phần tử thứ hai kế tiếp là a[jmax].
Sau khi xây dựng xong 2 mảng L và T:
Bắt đầu từ phần tử đầu tiên i=T[0].
T[T[0]] là phần tử thứ 2 đƣợc chọn
T[T[T[0]]] là phần tử thứ 3 đƣợc chọn
........
Tức là lúc đầu với i=T[0], ta chọn phần tử a[i], và các phần tử a[i] tiếp theo đƣợc chọn với i=T[i] (dựa vàng mảng vết T)
Quá trình truy vết có thể diễn tả nhƣ sau:
Xét a[j]
Xét a[i] (0≤i≤j)
Nếu a[i] L[jmax] thì:
int i=T[0];
{
jmax=j; L[i]=L[jmax] +1;
T[i] = jmax; // Lƣu vết vào mảng T
}
while( i != n+1) //Chừng nào chƣa duyệt đến aN+1
{
Thông báo chọn a[i]; i=T[i];
}
Ví dụ: với A = (7, 4, 5, 8, 6, 7, 10, 9, 11, 8). Hai mảng L và T sau khi tính sẽ là:
i
0
1
2
3
4
5
6
7
8
9
10
11
a[i]
-∞
7
4
5
8
6
7
10
9
11
8
+∞
L[i]
8
5
7
6
4
5
4
3
3
2
2
1
T[i]
2
4
3
5
7
6
7
9
9
11
11


Truy vết
Độ phức tạp của thuât toán O(n2)
#include #define inf int(1e9) #define N 1000
using namespace std;
int a[N+2], L[N+2], T[N+2];
int n, jmax; int main()
{
freopen("lis.inp", "r", stdin);
freopen("lis.out", "w", stdout);
 Cài đặt chƣơng trình:
cin>>n;
for(int i=1; i>a[i];
a[0] =-inf; a[n+1] =inf; L[n+1]=1;
for(int i=n; i>=0; i--)
{
jmax= n+1;
for(int j=i+1; j<=n+1; j++)
if(a[j] >a[i] && L[j] >L[jmax]) jmax=j; L[i]=L[jmax] +1;
T[i] = jmax; //Lưu vết vào mảng T
}
cout<<L[0] -2 <<"\n"; int i=T[0];
while( i != n+1)
{
cout<< a[i] <<" "; i=T[i];
}
return 0;
}
Cách 2:
 Công thức:
Phân rã bài toán:
Ta bổ sung 2 phần tử “lính canh” là a[0]= -∞ vào đầu dãy và a[n+1] = +∞ vào cuối dãy. Khi đó dãy con đơn điệu tăng dài nhất chắc chắn sẽ bắt đầu từ a[0] và kết thúc tại a[n]+1.
→ Cần tìm độ dài của dãy con tăng dài nhất từ a[0] →a[i]
Xây dựng hàm mục tiêu:
Gọi L[i] là độ dài của dãy con tăng dài nhất từ a[0] →a[i]
Suy ra kết quả của bài toán là: L[n+1] - 2
Bài toán cơ sở: Ta dễ dàng thấy đƣợc L[0] =1; L[1] =2 (Dãy con bắt đầu từ a[0]=-∞, dãy con này gồm 1 phần tử là -∞ nên L[0]=1. Phần tử tiếp theo L[1] chắc chắn thỏa mãn > -∞ nên dãy con tăng dài nhất lúc này L[1]=2)
Xây dựng công thức:
Xét a[i]:
Nếu a[j] <a[i] (với 0≤j<i) thì L[i] = max(L[i], L[j] +1)
(duyệt tất cả các a[j] ở trƣớc a[i] nếu mà a[j] <a[i], độ dài dãy con dài nhất tại thời điểm đó sẽ đƣợc nối thêm 1 phần tử vào sau dãy con dài nhất trƣớc đó
Truy vết:
Tại bƣớc xây dựng L, mỗi khi tính L[i] = L[j] + 1, ta đặt T[i] = j, để lƣu lại dãy con tăng dài nhất bắt đầu tại a[i] sẽ có phần tử thứ hai kế tiếp là a[jmax].
Sau khi xây dựng xong 2 mảng L và T:
Ta tạo 1 mảng lƣu các giá trị ta truy vết đƣợc
Bắt đầu từ phần tử đầu tiên i=T[n+1].
T[T[n+1]] là phần tử thứ 2 đƣợc chọn
T[T[T[n+1]]] là phần tử thứ 3 đƣợc chọn
........
Tức là lúc đầu với i=T[n+1], ta chọn phần tử a[i], và các phần tử a[i] tiếp theo đƣợc chọn với i=T[i] (dựa vàng mảng vết T)
Quá trình truy vết có thể diễn tả nhƣ sau:
Xét a[i]
Xét a[j] (0≤j≤i)
Nếu a[j] < a[i] và L[i] < L[j] +1 thì:
{
+ L[i] = L[j]+1
+ T[i]=j // phần tử trƣớc a[i] là a[j]
}
Duyệt từ phần tử cuối (i=n+1) về phần tử a[1]
{
Đẩy các a[i] đƣợc chọn vào vector (hoặc mảng) i=T[i];
}
Sau đó thông báo các phần tử đƣợc chọn.
Ví dụ: với A = (7, 4, 5, 8, 6, 7, 10, 9, 11, 8). Hai mảng L và T sau khi tính sẽ là:
i
0
1
2
3
4
5
6
7
8
9
10
11
a[i]
-∞
7
4
5
8
6
7
10
9
11
8
+∞
L[i]
1
2
2
3
4
4
5
6
6
7
6
8
T[i]

0
0
2
3
3
5
6
6
7
6
9
Truy vết
#include #define N 1000
#define inf int(1e9) using namespace std;
int a[N+2], L[N+2], T[N+2];
vector x; int n;
int main()
{
freopen("lis.inp","r",stdin);
freopen("lis.out","w",stdout); cin >> n;
for (int i=1; i> a[i];
a[0] = -inf; a[n+1] = inf;
L[0] = 1; L[1] = 2;
for (int i=2; i<=n+1; i++) for (int j=0; j<i; j++)
if (a[j] < a[i] && L[i] < L[j] + 1)
{
L[i] = L[j] + 1; T[i] = j;
}
cout 0; i=T[i])
x.push_back(a[i]);
 Cài đặt chƣơng trình:
for (int i=x.size() - 1; i>0; i--) cout << x[i] << " ";
return 0;
}
 Bài toán cùng dạng:
Đề bài: BCAKE (ĐỀ THI HSG TỈNH NGHỆ AN 2018)
An đã mua 𝑛 chiếc bánh, những chiếc bánh đƣợc đánh số theo thứ tự từ 1 đến 𝑛, mỗi chiếc bánh có dạng hình trụ và ta coi thể tích của chiếc bánh chính bằng thể tích của hình trụ, đƣợc tính theo công thức v = π.r2.h. Tuy nhiên nếu chỉ để 𝑛 chiếc bánh đơn l thì không có gì đặc biệt nên An muốn xếp những chiếc bánh thành một chiếc bánh nhiều tầng, hơn nữa còn phải là một chiếc bánh nhiều tầng có dạng tháp chổng ngƣợc Chiếc bánh thứ 𝑗 có thể xếp trên chiếc bánh thứ 𝑖 nếu 𝑗 > 𝑖 và thể tích của chiếc bánh thứ 𝑗 lớn hơn thể tích của chiếc bánh thứ 𝑖. Thể tích của chiếc bánh nhiều tầng bằng tổng thể tích những chiếc
bánh đơn l . Bạn hãy giúp An tính toán thể tích lớn nhất của chiếc bánh nhiều tầng mà cậu có thể xếp đƣợc.
Dữ liệu: Vào từ file BCAKE.INP
Dòng đầu tiên chứa số nguyên 𝑛 (1 ≤ 𝑛 ≤ 105 ). 𝑛 dòng tiếp theo, mỗi dòng chứa 2 số nguyên 𝑟𝑖, hi (1 ≤ 𝑟𝑖 ≤ 104; 1 ≤ hi ≤ 104) cách nhau bởi dấu cách, lần lƣợt là bán kính và chiều cao của chiếc bánh thứ 𝑖.
Kết quả: Ghi ra file BCAKE.OUT một số thực là thể tích lớn nhất tìm đƣợc, làm tròn
đến 3 chữ số sau dấu thập phân.
Ví dụ:
BCAKE.INP
BCAKE.OUT
BCAKE.INP
BCAKE.OU T
2
100 30
40 10
942477.796
4
1 1
9 7
1 4
10 7
3983.539
Hạn chế:
Có 20 số test ứng với 0 < n ≤ 20
Có 20 số test ứng với 20 < n ≤ 5000
Có 60 số test ứng với 5000 < n ≤ 105
Công thức:
+ Xây dựng hàm mục tiêu: L[i] là thể tích lớn nhất của chiếc bánh xếp chồng kết thúc tại a[i].
+ Bài toán cơ sở:
L[0] = -inf; L[1] = v[1];
+ Công thƣc: L[i] = max(L[j]) +v[i]
#include #define N int(1e5) #define inf int(1e9) #define ll long long using namespace std;
ll n, r[N+2], h[N+2];
double s[N+2], v[N+2], L[N+2];
int main()
{
freopen("bcake.inp","r",stdin);
freopen("bcake.out","w",stdout); cin>>n;
for(int i=1;i<=n;i++)
{
cin>> r[i]>>h[i];
v[i] = M_PI * r[i] * r[i] * h[i];
}
v[0]=-inf; v[n+1] = inf;
L[0] = -inf; L[1] = v[1];
for (int i=2; i<=n+1; i++) for (int j=0; j<i; j++)
if ( v[j] < v[i] && L[i] < L[j] + v[i]) L[i] = L[j] + v[i];
cout << setprecision(3) <<fixed<<L[n+1] - inf <<"\n";
Cài đặt chƣơng trình:
return 0;
}
Bài này giải bằng phƣơng pháp quy hoạch động + cấu trúc dữ liệu. Tuy nhiên Trong phần này tôi sử dụng quy hoạch động. Để full substak 3 thì phải kết hợp sử dụng cấu trúc dữ liệu.
Dạng bài toán Dãy con có tổng bằng S:
 Mô hình: Bài toán điển hình:
Cho dãy gồm n số nguyên dƣơng a1, a2, , an và một giá trị S.
Hãy chọn ra trong dãy một dãy con (không nhất thiết liên tiếp) có tổng bằng S. Input: SUMS.INP
Dòng 1 chứa số nguyên dƣơng n và S (1 ≤ n ≤ 100, 1 ≤ S ≤ 10000)
Dòng 2 chứa n số nguyên dƣơng a1, a2, , an (1 ≤ ai ≤ 100) Output: SUMS.OUT
Nếu có thể chọn ra đƣợc dãy con có tổng bằng S thì:
+ Dòng đầu ghi thông báo: “YES”
+ Dòng thứ hai đƣa ra dãy các vị trí của dãy con có tổng bằng S
SUMS.INP
SUMS.OUT
5 11
1 2 4 3 5
YES 2 3 5

Ngƣợc lại thì thông báo “NO” Ví dụ:
Cách giải và tìm hƣớng giải quyết tối ƣu cho bài toán:
Ta phân rã bài toán thành bài toán con: Tìm dãy con từ a[1] → a[i] có tổng bằng t.
Gọi L[i][t] =1 nếu tồn tại dãy con từ a[0] →a[i] có tổng bằng t.
Gọi L[i][t] =0 nếu không tồn tại dãy con từ a[0] →a[i] có tổng bằng t.
Ta có thể tính L[i][t] theo công thức:
L[i][t] = 1 (tạo đƣợc tổng t) nếu:L[i-1][t] =1 hoặc L[i-1][t-a[i]] = 1 L[i][t] = L[i-1][t] (nếu không tạo đƣợc tổng t)
Nhận xét: Nếu ta sử dụng công thức trên luôn thì cần sử dụng bảng phương án 2 chiều. Ta nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i-1. Ta có thể cải tiến là sử dụng bảng phư