Solução Zonas de Ataque Independentes

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:

  1. 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.
  2. 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.
  3. O intervalo tem tamanho menor que 3, retornamos 1.

Segue o código para melhor entendimento.


#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;
}

view raw

zonas.cpp

hosted with ❤ by GitHub