Bài F - Educational Codeforces Round 61 (Div .2)

Bài F:
Đề bài: Bạn được cho một xâu S có độ dài n bao gồm các ký tự Lattin. Bạn có tác động một vài thao tác đến xâu này: trong một thao tác bạn có thể xóa một vài xâu con gồm các kí tự liên tục của xâu này, nếu tất cả các kí tự trong xâu con bạn xóa bằng nhau. Ví dụ, sau khi xóa xâu con bbbb từ xâu abbbbaccdd chúng ta được xâu aaccdd.
  Tính số thao tác ít nhất để xóa tất cả các xâu.
Đầu vào:
+ Dòng đầu tiên chứa số n (1<=n<=500) - độ dài của xâu s
+ Dòng thứ 2 chứa xâu s (|s|=n) chứa các ký tự chữ cái Latin thường.
Đầu ra:
+ In ra 1 số - là kết quả cần tìm.
Ví dụ:
Đầu vào:
5
abaca
Đầu ra:
3
Đầu vào:
8
abcddcba
Đầu ra:
4.
Hướng dẫn:
Chúng ta giải bài toán này bằng quy hoạch động
Gọi dp(l,r) là câu trả lời cho xâu con s(l,l+1,...,r). Thì chúng ta có hai trường hợp:
1. Kí tự đầu tiên của xâu con được xóa tách biệt so với phần còn lại: dp(l,r)=1+dp(l+1,r)
2. Kí tự đầu tiên của xâu con bị xóa cùng với một số chữ cái khác thì dp(l,r)=min_(1<i<=r,s_i=s_r)dp(l+1,i-1)+dp(i,r).
Lời giải:

#include <bits/stdc++.h>
using namespace std;

const int N = 550;

char s[N];

int a[N], dp[N][N], cp[N][N];
int main() {
 ios::sync_with_stdio(0);
 cin.tie(0); cout.tie(0);
 int n; cin >> n;
 cin >> s + 1;
 int ca = 0;
 for (int i = 1; i <= n; i++) {
  if (i == n || s[i] != s[i + 1]) a[++ca] = s[i] - 'a';
 }
 n = ca;
 for (int len = 1; len <= n; len++) {
  for (int i = 1; i + len - 1 <= n; i++) {
   int j = i + len - 1;
   dp[i][j] = 1e9;
   if (a[i] == a[j]) {
    dp[i][j] = min(dp[i][j], cp[i][j - 1] + 1);
   }                                                                                                            
   for (int k = i; k < j; k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
   cp[i][j] = min(dp[i][j], dp[i + 1][j]);
   for (int k = i + 1; k <= j; k++) if (a[k] == a[i]) {
    cp[i][j] = min(cp[i][j], cp[i][k - 1] + cp[k][j]);
   }
  }
 }
 cout << dp[1][n] << endl;
 return 0;
}