Solução por João Guilherme
Temos novamente um problema de Programação dinâmica. Nesse faremos uma dp com os estados começo do intervalo e fim do intervalo. Para cada intervalo temos alguns casos:
- O intervalo tem tamanho maior que 3. Nesse caso olhamos para cada 2 outras posições entre o começo e o fim do intervalo, checamos se não temos 3 vermelhos, caso não tenha nós adicionamos à solução o produto entre as soluções dos 3 intervalos que serão formados pelos nossos 4 pontos.
- O intervalo tem tamanho igual a 3. Então basta checarmos se o intervalo é válido (tem menos que 3 vermelhos) e respondemos de acordo.
- O intervalo tem tamanho menor que 3, retornamos 1.
Segue o código para melhor entendimento.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <string> | |
| #include <iostream> | |
| using namespace std; | |
| int circle[50], n; | |
| string input; | |
| long long int dp[50][50]; | |
| long long int f(int a, int b){ | |
| if(dp[a][b] != -1) return dp[a][b]; | |
| if(b - a <= 1) return dp[a][b] = 1LL; | |
| if(b - a == 2){ | |
| //cout << a << " " << b << endl; | |
| if(circle[a] + circle[a + 1] + circle[b] >= 2) return dp[a][b] = 0LL; | |
| else return dp[a][b] = 1LL; | |
| } | |
| dp[a][b] = 0; | |
| for(int i = a + 1; i <= b; i += 3){ | |
| for(int j = i + 1; j <= b; j += 3){ | |
| //cout << a << " " << i << " " << j << " " << b << endl; | |
| if(circle[a] + circle[i] + circle[j] < 2) | |
| dp[a][b] += (f(a + 1, i - 1)*f(i + 1, j - 1)*f(j + 1, b)); | |
| } | |
| } | |
| return dp[a][b]; | |
| } | |
| int main(){ | |
| int t; | |
| scanf("%d", &t); | |
| for(int c = 1; c <= t; ++c){ | |
| scanf("%d", &n); | |
| for(int i = 0; i < 50; ++i) | |
| for(int j = 0; j < 50; ++j) dp[i][j] = -1; | |
| cin >> input; | |
| for(int i = 0; i < input.size(); ++i) circle[i + 1] = (input[i] == 'R')?1:0; | |
| printf("Case %d: %lld\n", c, f(1, n)); | |
| } | |
| return 0; | |
| } |