Cod sursa(job #613650)

Utilizator cezar305Mr. 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;
}