Cod sursa(job #2330839)
Utilizator | Data | 28 ianuarie 2019 21:07:20 | |
---|---|---|---|
Problema | Culori | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.69 kb |
#include<fstream>
#define MOD 9901
using namespace std;
ifstream fi("culori.in");
ofstream fo("culori.out");
int n,i,j,k,A[520],Dp[520][520];
int main()
{
fi>>n;
for(i=1; i<=2*n-1; i++)
fi>>A[i];
for(i=1; i<=2*n-1; i++)
Dp[i][i]=1;
for(i=2*n-1; i>=1; i--)
{
for(j=i; j<=2*n-1; j+=2)
{
if(A[i]==A[j])
{
for(k=i+1; k<j; k+=2)
{
if(A[i+1]==A[k])
Dp[i][j]=(Dp[i][j]+((Dp[i+1][k]*Dp[k+1][j])%MOD))%MOD;
}
}
}
}
fo<<Dp[1][2*n-1]<<"\n";
fi.close();
fo.close();
return 0;
}