tag: range dp, bitset, bitset tree, sentai decomposition.

Để việc giải thích đơn giản hơn thì với bộ dữ liệu thứ $i$, đặt $N=S_i$.

Subtask 1:

Ta cần chuẩn bị mảng $palin[i][j]$, nếu $palin[i][j]=1$ thì đoạn $[i..j]$ là xâu đối xứng, không thì ngược lại. Ta có thể làm điều đó trong $O(N^2)$, với công thức truy hồi $palin[i][j]=palin[i+1][j-1]$ AND $(s[i]==s[j])$.

Khi đó, bài toán chỉ đơn thuần là một bài quy hoạch động cổ điển. Gọi $dp[i][j]$ là số chi phi ta giảm được khi thực hiện cả thao tác $(1)$ và $(2)$ trên đoạn $[i,j]$ thay vì chỉ sử dụng thao tác $(1)$. Ví dụ với xâu AAAA, thì $dp[1][4]=1$ vì ta có thể xây dựng được xâu trong $3$ thao tác, thay vì $4$ nếu chỉ sử dụng thao tác $(1)$.

Nếu $2|(j-i+1)$, ta đặt $m=\frac{i+j-1}{2}$. Khi đó, công thức truy hồi là $dp[i][j]=max(dp[i+1][j],dp[i][j-1],palin[i][j]\times (dp[i][m]+(m-i)))$.

Đáp án sẽ là $N-dp[1][n]$. Ta có thể thực hiện phần quy hoạch động này trong $O(N^2)$.

Độ phức tạp: $O(T\times N^2)$.

Subtask 2:

Với $N=5\ast {10}^4$, thuật toán của chúng ta ở Subtask 1 sẽ bị chạy quá thời gian, vì vậy ta cần tăng tốc độ cho quy hoạch động.

Ta nhận thấy rằng cấu trúc dữ liệu bitset có thể tăng tốc độ của thuật toán của ta lên $32$ lần, nhưng như vậy là chưa đủ, vì bây giờ chương trình vẫn chạy trong khoảng $\frac{T\ast N^2}{32}=8\times {10}^9$ phép tính, vẫn còn quá nhiều.

Ta sẽ sử dụng bitset hai lần, làm tăng tốc độ thuật toán lên ${32}^2=1024$ lần. Như vậy, bây giờ chương trình sẽ chạy trong khoảng $\frac{T\ast N^2}{{32}^2}=2.5\times {10}^8$ phép tính. Trên thực tế, thuật toán chạy rất nhanh, vì chúng ta chỉ xét những xâu đối xứng có độ dài chẵn. Đây chính là kỹ thuật Sentai Decomposition.

Độ phức tạp: $O(\frac{T\ast N^2}{{32}^2})$