Cod sursa(job #1562683)
Utilizator | Data | 5 ianuarie 2016 13:19:08 | |
---|---|---|---|
Problema | Culori | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.65 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("culori.in");
ofstream cout("culori.out");
const int LIM=512, MOD=9901;
int n, v[LIM], dp[LIM][LIM];
int main()
{
cin>>n;
n=2*n-1;
for(int i=1; i<=n; ++i)
cin>>v[i];
for(int i=1; i<=n; ++i)
dp[i][i]=1;
for(int lg=3; lg<=n; lg+=2)
for(int i=1; i<=n-lg+1; ++i)
{
int j=i+lg-1;
if(v[i]==v[j])
for(int k=i+1; k<j; k+=2)
if(v[i]==v[k+1])
dp[i][j]=(dp[i][j]+dp[i+1][k]*dp[k+1][j])%MOD;
}
cout<<dp[1][n];
return 0;
}