Cod sursa(job #637941)

Utilizator sodamngoodSo Damn Good sodamngood Data 20 noiembrie 2011 17:41:19
Problema PalM Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 1.41 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 512

int N, sol;
int nextst[maxn][30], nextdr[maxn][30];
int D[maxn][maxn];
char A[maxn];

int main() {
    FILE *f1=fopen("palm.in", "r"), *f2=fopen("palm.out", "w");
    int i, j, l, p;

    fscanf(f1, "%s\n", A+1);
    N = strlen(A+1);

    for(i=1; i<=N; i++) {
         for(j='a'-'a'; j<='z'-'a'; j++) {
              for(p=i-1; p>=1; p--) {
                   if(j == A[p] - 'a') {
                        nextst[i][j] = p;
                        break;
                   }
              }
              for(p=i+1; p<=N; p++) {
                   if(j == A[p] - 'a') {
                        nextdr[i][j] = p;
                        break;
                   }
              }
         }
    }

    for(l=1; l<=N; l++) {
         for(i=1; i<=N; i++) {
              if(i+l-1 > N) break;
              if(A[i] != A[i+l-1]) continue;

              D[i][i+l-1] = max(D[i][i+l-1], min(2, l));

              for(j='a'-'a'; j<=A[i]-'a'; j++) {
                   D[ nextst[i][j] ][ nextdr[i+l-1][j] ] = max(D[ nextst[i][j] ][ nextdr[i+l-1][j] ], D[i][i+l-1] + 2);
              }
         }
    }

    for(l=1; l<=N; l++) {
         for(i=1; i<=N; i++) {
              if(i+l-1 > N) break;

              sol = max(sol, D[i][i+l-1]);
         }
    }

    fprintf(f2, "%d\n", sol);

    fclose(f1); fclose(f2);
    return 0;
}