Pagini recente » Cod sursa (job #76389) | Cod sursa (job #2644215) | Cod sursa (job #1117386) | Cod sursa (job #853361) | Cod sursa (job #613650)
Cod sursa(job #613650)
Utilizator |
Mr. Noname cezar305 |
Data |
2 octombrie 2011 17:59:28 |
Problema |
PalM |
Scor |
Ascuns |
Compilator |
cpp |
Status |
done |
Runda |
|
Marime |
1.18 kb |
#include <cstdio>
const int N = 505, A = 27;
char a[N], b[N];
int n, d[N][N][A], maxd[N][N][A];
void inverseaza(char b[N], char a[N]) {
for (int i = 1; i <= n; ++i)
b[i] = a[n - i + 1];
}
inline int max(int x, int y) {
return x > y ? x : y;
}
// d[i][j][k] = cel mai lung subsir comun al sirurilor a[1]...a[i] si
// b[1]...b[j] care se termina in pozitia k
void solve() {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n - i + 1; ++j) {
if (a[i] == b[j])
d[i][j][a[i] - 'a'] = maxd[i - 1][j - 1][a[i] - 'a'] + 1;
for (int k = 0; k <= 25; ++k) {
if (!(a[i] == b[j] && k == a[i] - 'a'))
d[i][j][k] = max(d[i - 1][j][k], d[i][j - 1][k]);
if (k == 0)
maxd[i][j][k] = d[i][j][k];
else
maxd[i][j][k] = max(maxd[i][j][k - 1], d[i][j][k]);
}
}
int rez = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n - i + 1; ++j)
rez = max(rez, maxd[i][j][25]);
printf("%d\n", 2 * rez - 1);
}
int main() {
freopen("palm.in", "r", stdin);
freopen("palm.out", "w", stdout);
gets(a + 1);
for (int i = 1; a[i]; ++i)
n = i;
inverseaza(b, a);
solve();
return 0;
}