Este problema puede resolverse mediante programación dinámica (no es difícil de resolver, porque el problema se ubica en el tema “programación dinámica” 🙂).
Comencemos con un problema diferente. Digamos que tiene dos cadenas, S1 y S2, y desea encontrar varias formas de borrar algunos caracteres de ellas de tal manera que las cadenas resultantes sean iguales.
Esta tarea también se trata de programación dinámica. Puede calcular dp [i] [j]: varias formas de eliminar algunos caracteres del prefijo de la primera cadena que tiene una longitud i y algunos caracteres del prefijo de la segunda cadena con una longitud j, de modo que las cadenas restantes sean iguales (aquí consideramos solo cadenas formadas por caracteres restantes en el prefijo, sin tener en cuenta el sufijo). Para calcular dp [i] [j] tampoco puede tomar un par de caracteres en las posiciones i, j, entonces tiene dp [i] [j] = dp [i-1] [j] + dp [i] [j-1] -dp [i-1] [j-1]; sumaste resultados para (i-1, j) y (i, j-1); todas las subsecuencias que contienen st1 [i] o st2 [j] se contarán exactamente una vez, todas las demás subsecuencias se contarán dos veces, por lo que debe restar dp [i-1] [j-1]. O también puede tomar un par de caracteres en las posiciones i, j (que es posible solo si son iguales), en este caso tiene dp [i] [j] + = dp [i-1] [j-1].
- Cómo resolver un problema de programación difícil por mi cuenta
- ¿Existen algoritmos en R que permitan clasificar una variable binaria basada en un conjunto de cadenas (texto)?
- ¿Qué proyectos usan algoritmos de redes neuronales?
- ¿Cuál es la diferencia principal entre algoritmo y pseudocódigo?
- ¿Cuál es la diferencia entre tener un buen algoritmo y no tener uno?
Ahora es el momento de usar el problema anterior para resolver nuestra tarea original de alguna manera.
Elegir subsecuencia cuadrada es igual a dividir su cadena en dos partes y luego elegir dos subsecuencias iguales en estas partes, ¡y ya sabemos cómo contar el número de formas de elegir dos subsecuencias iguales! 🙂 Parece que podemos probar todas las divisiones posibles de nuestra cadena en dos partes, contar el número de formas de elegir dos subsecuencias iguales para cada división y sumarlas para obtener un resultado. No exactamente. Nos perdimos una cosa más. Para algunas subsecuencias cuadradas, las contaremos para cada división posible entre la última letra de la primera parte y la primera letra de la segunda parte. Esto también es fácil de arreglar. En lugar de comenzar con el caso base dp [0] [0] = 1, diremos que la primera letra de la segunda cadena debe tomarse en la subsecuencia resultante; puede manejarse comenzando a llenar la tabla DP desde los estados correspondientes. Ahora, cada par de subsecuencias solo se contará una vez, para una división justo antes del primer carácter de la segunda subsecuencia.
Y aquí hay un código:
#include
#define bs 1000000007
usando el espacio de nombres estándar;
pruebas int;
int ans;
int dp [500] [500];
int resolver (cadena st1, cadena st2)
{
para (int i = 0; i <= st1.size (); i ++)
{
para (int j = 0; j <= st2.size (); j ++)
{
dp [i] [j] = 0;
}
}
para (int i = 0; i <st2.size (); i ++)
{
if (st2 [i] == st1 [0])
dp [1] [i + 1] = 1;
si yo)
dp [1] [i + 1] + = dp [1] [i];
}
para (int i = 1; i <st1.size (); i ++)
{
para (int j = 0; j <st2.size (); j ++)
{
dp [i + 1] [j + 1] = dp [i + 1] [j] + dp [i] [j + 1] – dp [i] [j];
if (st1 [i] == st2 [j])
{
dp [i + 1] [j + 1] + = dp [i] [j];
}
dp [i + 1] [j + 1] = (dp [i + 1] [j + 1]% bs);
si (dp [i + 1] [j + 1] <0)
dp [i + 1] [j + 1] + = bs;
}
}
return dp [st1.size ()] [st2.size ()];
}
int main () {
ios_base :: sync_with_stdio (0);
//cin.tie(0);
cin >> pruebas;
para (; pruebas; –prueba)
{
ans = 0;
cuerda st;
cin >> st;
para (int cp = 1; cp <st.size (); cp ++)
{
cadena st1, st2;
para (int i = 0; i <st.size (); i ++)
{
si (i <cp)
st1 + = st [i];
más
st2 + = st [i];
}
ans + = resolver (st2, st1);
ans% = bs;
}
cout << ans << endl;
}
devuelve 0;
}
