Cod sursa(job #2337171)
Utilizator | Trisca Vicol Cezar triscacezar | Data | 5 februarie 2019 23:02:43 |
---|---|---|---|
Problema | Culori | Scor | 4 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.65 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
const int mod=9901;
int n,i,c[1010],dyn[1010][1010];
int main()
{
f>>n;
for(i=1;i<=2*n-1;i++)
f>>c[i],dyn[i][i]=1;
for(int len=3;len<=2*n-1;len+=2)
{
for(i=1;i+len-1<=2*n-1;i++)
if(c[i]==c[i+len-1])
{
dyn[i][i+len-1]=dyn[i+1][i+len-2];
for(int j=i+2;j<=i+len-3;j++)
if(c[i]==c[j])
dyn[i][i+len-1]=(dyn[i][i+len-1]+dyn[i][j]*dyn[j][i+len-1])%mod;
}
}
g<<dyn[1][2*n-1];
return 0;
}