Cod sursa(job #478730)
Utilizator | Data | 20 august 2010 09:39:48 | |
---|---|---|---|
Problema | Culori | Scor | 44 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.55 kb |
#include<fstream>
using namespace std;
const char iname[]="culori.in";
const char oname[]="culori.out";
const int maxn=505;
const int mod=9901;
ifstream f(iname);
ofstream g(oname);
int a[maxn],dp[maxn][maxn],i,j,n,k;
int main()
{
f>>n;
n=n*2-1;
for(i=1;i<=n;++i)
f>>a[i],dp[i][i]=1;
for(i=1;i<n;++i)
for(j=n-i;j;--j)
if(a[j+i]==a[j])
for(k=j+1;k<j+i;++k)
if(a[k]==a[j+1])
dp[j][j+i]=(dp[j][j+i]+dp[j+1][k]*dp[k+1][j+i])%mod;
g<<dp[1][n]<<"\n";
}