Pagini recente » Cod sursa (job #2149956) | Istoria paginii runda/cerculdeinfo-lectia6-arbori | Cod sursa (job #1490408) | Cod sursa (job #1490783) | Cod sursa (job #637728)
Cod sursa(job #637728)
#include<stdio.h>
#include<string.h>
#define MaxN 510
#define MaxS 31
int N,MAX,c,A[MaxN][MaxN][MaxS],B[MaxN];
char S[MaxN],S2[MaxN];
int max(int a,int b)
{
return a>b ? a:b;
}
void cmlsc(int N,int M)
{
int MAX;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
{
for(int k=0;k<=26;k++)
A[i][j][k] = max(A[i-1][j][k],A[i][j-1][k]);
MAX = 0;
if(S[j-1] == S2[i-1])
{
for(int k=0;k<=S2[i-1]-'a';k++)
if(A[i-1][j-1][k] > MAX)
MAX = A[i-1][j-1][k];
}
else
MAX = A[i][j][S2[i-1]-'a']-1;
A[i][j][S2[i-1]-'a'] = MAX+1;
}
}
void Ad(int a,int b)
{
for(int j=1;j<=a;j++)
for(int k=1;k<=b;k++)
for(int l=0;l<=26;l++)
A[j][k][l] = 0;
}
int BeB(int a,int b)
{
for(int i=0;i<=26;i++)
if(A[a-1][N-a-1][i] <= A[b-1][N-b-1][i])
return 0;
return 1;
}
int main()
{
FILE *f = fopen("palm.in","r");
FILE *g = fopen("palm.out","w");
fgets(S,sizeof(S),f);
N = strlen(S);
for(int i=0;i<N;i++)
S2[N-i-2] = S[i];
cmlsc(N,N);
for(int i=1;i<=N;i++)
{
for(int j=0;j<=S[i-1]-'a';j++)
if(A[N-i][i-1][j] > B[i])
B[i] = A[N-i][i-1][j];
}
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(S[i-1] == S[j-1] && B[i] == B[j]-1 && MAX < 2*B[j])
MAX = 2*B[j], c = j;
B[c] = 0;
for(int i=1;i<=N;i++)
if(MAX < 2*B[i]+1)
MAX = 2*B[i]+1;
fprintf(g,"%d ",MAX);
fclose(g);
fclose(f);
return 0;
}