1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)
#define lowbit(x) ((x)&-(x))
#define eb emplace_back
#define SZ(x) (int)((x).size())
#define ll long long
#define vt vector
#define fr first
#define se second
#define mmt(x, y) memset(x, y, sizeof x)
#define PII pair<int, int>
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})
constexpr int N = 700 + 10;
char s[N];
int dp[N][N], a[N][N], b[N][N], n, u;
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> s + 1, mmt(dp, 0x3f);
FL(i, 1, n)dp[i][i] = 1;
FL(i, 1, n)FL(j, i, n){
int flag = 1;
for(int k = 0; i + k <= j && j + k <= n; k++)
if(s[i + k] != s[j + k + 1]){flag = 0;break;}
if(flag)a[i][j] = 1, b[i][j] = i;
}
FR(i, n, 1)FL(j, i + 1, n)FL(k, i, j){
cmin(dp[i][j], dp[i][k] + dp[k + 1][j]), u = b[i][k];
if(u && a[u][k] && k - u + 1 == j - k)
cmin(dp[i][j], dp[i][k]), b[i][j] = k + 1;
}
cout << dp[1][n] << endl;
return 0;
}
|
