Solutions of Concating substring - MarisaOJ: Marisa Online Judge

Solutions of Concating substring

Select solution language

Write solution here.


User Avatar viiking    Created at    1 likes

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 ; }