Cod sursa(job #2138107)
Utilizator | Bogdan Pop Bodo171 | Data | 21 februarie 2018 12:55:48 |
---|---|---|---|
Problema | Culori | Scor | 84 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.61 kb |
#include <iostream>
#include <fstream>
using namespace std;
const int mod=9901;
const int nmax=517;
int v[nmax],dp[nmax][nmax];
int len,i,j,n,nr,prod;
int main()
{
ifstream f("culori.in");
ofstream g("culori.out");
f>>n;nr=2*n-1;
for(i=1;i<=nr;i++)
f>>v[ i ];
for(i=1;i<=nr;i++)
dp[1][i]=1;
for(len=2;len<=nr;len++)
for(i=1;i<=nr-len+1;i++)
if(v[i]==v[i+len-1])
{
for(j=i;j<=i+len-1;j++)
if(v[j]==v[i])
dp[len][i]=(dp[len][i]+dp[j-i-1][i+1]*dp[len-j+i][j])%mod;
}
g<<dp[nr][1];
return 0;
}