Parole_saturnine

#include <cstdio>
const int MAXM=1005;

int N, M, S[MAXM], mem[MAXM][MAXM];

int solve(int,int);

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);

    for(int i=0; i<MAXM; i++)
            for(int j=0; j<MAXM; j++)
                    mem[i][j]=-1;

    scanf("%d %d", &M, &N);

    for(int i=1; i<=M; i++) scanf("%d", S+i);

    printf("%d\n", solve(0,0));

    return 0;
}

int solve(int n, int s)
{
    if(mem[n][s]!=-1) return mem[n][s];
    if(s==M) return mem[n][s]=0;
    if(n==N) return mem[n][s]=1;

    //Estendo il matching
    int a=solve(n+1,s+1);

    //Annullo il matching corrente calcolando quello nuovo
    int nuovaLettera=(S[s+1]==1)? 0:1, i, nuovaS;
    bool found=false;

    for(nuovaS=s; nuovaS>0 && !found; nuovaS--){
        if(S[nuovaS]==nuovaLettera)
            for(i=1, found=true; i<nuovaS && found; i++)
                 if(S[s+1-i]!=S[nuovaS-i]) found=false;
    }

    int b=solve(n+1,nuovaS);

    return mem[n][s]=(a+b)%2011;
}