zapis.cpp

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#define long long long

int n;

char a[12309];

int c[234][234];

long F[234][234];

int FF[234][234];

bool big=false;

long f(int ll, int rr){

    if (ll>rr) return 1;

    if (FF[ll][rr]++) return F[ll][rr];

    long r=0;

    for (int i=ll+1; i<=rr; i+=2)

    r += c[a[ll]][a[i]] * f(ll+1, i-1) * f(i+1, rr);

    //printf("f(%d, %d) = %d\n", ll, rr, r);

    if (r>=100000) big=true;

    return F[ll][rr] = r%100000;

}

main(){

    c['['][']']=1;

    c['('][')']=1;

    c['{']['}']=1;

    c['?']['?']=3;

    c['?'][']']=1;

    c['?'][')']=1;

    c['?']['}']=1;

    c['[']['?']=1;

    c['(']['?']=1;

    c['{']['?']=1;

    scanf("%d%s", &n, a+1);

    f(1,n);

    if (big) printf("%05lld\n", f(1, n));

    else printf("%lld\n", f(1, n));

}

Nhận xét

Mô tả

Các lỗi thường gặp