TOI11: Segitiga

#include<stdio.h>
int const N = 257;
char str[257];
bool dp[257][257][3];
bool vst[257][257][3];

bool cal(int L,int R,int val){
//  printf("Test (%d,%d)%d\n",L,R,val);
    if(L == R){
        return str[L]-'0' == val;
    }
    if(R - L == 1){
        if(val == 0){
            return (str[L] == '0' && str[R] == '2');
        }
        else if(val == 1){
            return  (str[L] == '0' && str[R] == '1')||
                    (str[L] == '1' && str[R] == '1')||
                    (str[L] == '1' && str[R] == '2')||
                    (str[L] == '2' && str[R] == '0')||
                    (str[L] == '2' && str[R] == '2');
        }
        else if(val == 2){
            return  (str[L] == '0' && str[R] == '0')||
                    (str[L] == '1' && str[R] == '0')||
                    (str[L] == '2' && str[R] == '1');
        }
        else{
            printf("error (%d,%d) %d\n",L,R,val);
            return false;
        }
    }
    if(vst[L][R][val])return dp[L][R][val];
    vst[L][R][val] = true;
    bool ans = false;
    for(int m = L ; m < R && !ans ; m ++){
        if(val == 0){
            ans |= (cal(L,m,0) && cal(m+1,R,2));
        }
        else if(val == 1){
            ans |=  (cal(L,m,0) && cal(m+1,R,1))||
                    (cal(L,m,1) && cal(m+1,R,1))||
                    (cal(L,m,1) && cal(m+1,R,2))||
                    (cal(L,m,2) && cal(m+1,R,0))||
                    (cal(L,m,2) && cal(m+1,R,2));
        }
        else if(val == 2){
            ans |=  (cal(L,m,0) && cal(m+1,R,0))||
                    (cal(L,m,1) && cal(m+1,R,0))||
                    (cal(L,m,2) && cal(m+1,R,1));
        }
    }
    //printf("Test [%d,%d] need %d - > %s\n",L,R,val,(ans ? "true" : "false"));
    return dp[L][R][val] = ans;
}

int main()
{
    for(int t = 0 ; t < 20 ; t ++){
        int n;
        for(int i = 0 ; i < 257 ; i ++)for(int j = 0 ; j < 257 ; j ++)for(int k = 0 ; k < 3 ; k ++)vst[i][j][k] = false;
        scanf("%d",&n);
        scanf(" %s",str);
        printf("%s\n",cal(0,n-1,0) ? "yes" : "no");
    }
    return 0;
}