Bài này việc khó nhất là nghĩ ra trạng thái để chúng ta quy hoạch động , một khi các bạn đã nghĩ ra
rồi thì việc suy nghĩ công thức chuyển trạng thái cũng như tối ưu thời gian , bộ nhớ sẽ khá đơn
giản .
Vậy bài này nên định nghĩa hàm quy hoạch động như thế nào ?
Dễ thấy , chiều thứ nhất chắc chắc là chiều " i " thường thấy ở bao bài quy hoạch động ,
ngoài ra ta cần biết được thêm một chiều mà mình đặt là " j " đại diện cho trạng thái hiện
tại đã khớp được chính xác j kí tự . Chưa hết vì đề bài yêu cầu chọn ra k xâu nên ta cũng cần
một chiều thứ 3 " z ", chiều này trả lời cho câu hỏi trạng thái hiện tại đã chọn được bao nhiêu xâu ,
cuối cùng vì ta cần chọn ra k xâu không giao nhau , do đó cần thêm 1 chiều cuối cùng " ok" để phân
biệt được rằng liệu ta đang trong 1 đoạn liên tục hay đã kết thúc một đoạn và chuẩn bị qua đoạn
tiếp theo .
0 <= i <= n
0 <= j <= m
0 <= z <= k
0 <= ok <= 1
Qua đó ta có 1 hàm quy hoạch động f(i , j , z , ok) được định nghĩa hoàn chỉnh như sau :
Số cách để ghép khi đã xét xong i kí tự đầu tiên của xâu A , đồng thời đã khớp được j kí tự
đầu tiên của xâu B và dùng chính xác z đoạn con , đoạn con hiện tại đang tiếp diễn nếu ok == 1 ,
ngược lại ok == 0 .
Phần chuyển trạng thái sẽ hơi dài dòng nhưng khá dễ hiểu , các bạn có thể thử tự tư duy tại sao lại chuyển trạng thái
như vậy , đây là code mẫu của mình , ở đây mình dùng 2 mảng dp để tiết kiệm bộ nhớ , nếu không
thì chắc chắc sẽ chạy sinh lỗi vì ta phải lưu 1 mảng dp 4 chiều kích cỡ 1001 * 201 * 201 * 2 .
Độ phức tạp : O(n * m * k * 2) xấp xỉ 8 * 10^7 , khá thở oxi rồi :))
### Code mẫu
```cpp
#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define BIT(x , i) (((x) >> (i)) & 1)
#define MASK(i) (1ll << (i))
#define pb push_back
#define LOG 20
#define endl '\n'
template <class X , class Y>
bool minimize(X& x , const Y& y) {
if(x > y) {
x = y ;
return true ;
}
return false ;
}
template <class X , class Y>
bool maximize(X& x , const Y& y) {
if(x < y) {
x = y ;
return true ;
}
return false ;
}
const int MOD = 1e9 + 7 ;
int dpCur[201][201][2] , dpPrev[201][201][2] ;
void process(void) {
int n , m , kkk ; cin >> n >> m >> kkk ;
string a , b ; cin >> a >> b ;
// dp(i , j , k , 01) : xet i ki tu dau tien cua a , da khop j ki tu , da chon k doan con , dang o giua 1 doan con hay khong
a = "." + a , b = "." + b ;
dpPrev[0][0][0] = 1 ;
for(int i = 0 ; i < n ; ++i) {
for(int j = 0 ; j <= m ; ++j) for(int k = 0 ; k <= kkk ; ++k) dpCur[j][k][0] = dpCur[j][k][1] = 0 ;
for(int j = 0 ; j <= m ; ++j) for(int k = 0 ; k <= kkk ; ++k) for(int isClose = 0 ; isClose <= 1 ; ++isClose) {
if(dpPrev[j][k][isClose] == 0) continue ;
// bat dau mot doan moi
if(isClose == 0) {
dpCur[j][k][0] += dpPrev[j][k][0] ;
dpCur[j][k][0] %= MOD ;
if(k + 1 <= kkk && j + 1 <= m && a[i + 1] == b[j + 1]) {
dpCur[j + 1][k + 1][1] += dpPrev[j][k][0] ;
dpCur[j + 1][k + 1][1] %= MOD ;
}
}
// tiep tuc 1 doan
else {
dpCur[j][k][0] += dpPrev[j][k][1] ;
dpCur[j][k][0] %= MOD ;
if(j + 1 <= m && k + 1 <= kkk && a[i + 1] == b[j + 1]) {
dpCur[j + 1][k + 1][1] += dpPrev[j][k][1] ;
dpCur[j + 1][k + 1][1] %= MOD ;
}
if(j + 1 <= m && a[i + 1] == b[j + 1]) {
dpCur[j + 1][k][1] += dpPrev[j][k][1] ;
dpCur[j + 1][k][1] %= MOD ;
}
}
}
swap(dpCur , dpPrev) ;
}
int res = 0 ;
for(int ok = 0 ; ok <= 1 ; ++ok) {
res += dpPrev[m][kkk][ok] ;
res %= MOD ;
}
cout << res << endl ;
}
int32_t main(void) {
ios_base :: sync_with_stdio(false) ;
cout.tie(nullptr) ;
cin.tie(nullptr) ;
process() ;
return 0 ;
}
viiking
Created at
1 likes