Cod sursa(job #18767)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 18 februarie 2007 14:00:00
Problema Culori Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <stdio.h>

#define mod 9901
#define maxn 520

int n;
int c[maxn][maxn];
int a[maxn];

int main()
{
    freopen("culori.in","r",stdin);
    freopen("culori.out","w",stdout);

    int i,j,l,k;
    
    scanf("%d",&n);
    n=2*n-1;
    
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    
    for (i=1;i<=n;i++) c[i][i]=1;
    
	for (l=1;l<=n;l++)
	  for (i=1;i+l-1<=n;i++)
		 if (a[i]==a[i+l-1])
		 {
			j=i+l-1;
			for (k=i;k<=j;k++)
			{
				c[i][j]+=c[i+1][k-1]*c[k][j];
				c[i][j]%=mod;
			}
		 }

    printf("%d\n",c[1][n]);
    
    return 0;
}