Cod sursa(job #635577)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 19 noiembrie 2011 13:19:17
Problema PalM Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 0.95 kb
#include <fstream>
#include <string>
#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;
    for (i=1;i<=B;i++)
        if (c[i]>l)
            l=c[i];
    return l;
}

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++)
            if (v[j]<=v[i]) a[++A]=v[j];
        for (j=n;j>i;j--)
            if (v[j]<=v[i]) b[++B]=v[j];
        sol=max(sol,2*LCIS(A,B)+1);
    }
    g << sol << '\n';
    f.close();g.close();
    return 0;
}