Cod sursa(job #635689)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 19 noiembrie 2011 14:11:23
Problema PalM Scor 10
Compilator cpp Status done
Runda .com 2011 Marime 1 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream f("palm.in");
ofstream g("palm.out");

string s;
int i,n,v[501],sol=0,j,a[501],A,b[501],B;

int LCIS (int A,int B) {
    int cr,l,i,j;
    vector <int> c(501,0);
    for (i=1;i<=A;i++) {
        cr=0;
        for (j=1;j<=B;j++) {
            if (a[i]==b[j] && cr+1>c[j])
                c[j]=cr+1;
            if (b[j]<=a[i] && cr<c[j])
                cr=c[j];
        }
    }
    l=0;
    int index=-1;
    for (i=1;i<=max(A,B);i++)
        if (c[i]>l) {
            l=c[i];
            if (i==A) index=A;
        }
    if (index==A) return 2*l;
    return 2*l+1;
}


int main () {
    f >> s;
    n=s.size();
    for (i=1;i<=n;i++) v[i]=int(s[i-1])-int('a')+1;
    for (i=2;i<n;i++) {
        A=B=0;
        for (j=1;j<=i;j++) a[++A]=v[j];
        for (j=n;j>i;j--) b[++B]=v[j];
        sol=max(sol,LCIS(A,B));
    }
    g << sol << '\n';
    f.close();g.close();
    return 0;
}