-
Notifications
You must be signed in to change notification settings - Fork 1
/
LightOJ 1033.cpp
53 lines (39 loc) · 943 Bytes
/
LightOJ 1033.cpp
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define iter(i, a, b) for(int i = (a) ; i < (b) ; i++)
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef pair< int , int > pii;
typedef pair< int , pii > iii;
typedef vector< pii > vii;
#define INF (1 << 29)
#define pi (2.0 * acos(0.0))
#define MAXX 105
string str;
int dp[MAXX][MAXX];
int solve(int i, int j){
if(i >= j)
return 0;
if(dp[i][j] != -1)
return dp[i][j];
if(str[i] == str[j])
dp[i][j] = solve(i + 1, j - 1);
else
dp[i][j] = 1 + min(solve(i + 1, j), solve(i, j - 1));
return dp[i][j];
}
int main(){
//READ("LightOJ 1033.txt");
int tc, case_no = 0;
scanf("%d", &tc);
while(tc--){
cin>>str;
mem(dp, -1);
int res = solve(0, str.size() - 1);
printf("Case %d: %d\n", ++case_no, res);
}
return 0;
}