Será la programación dinámica. Tenga en cuenta que el límite es lo suficientemente pequeño (500 para el grande), tenemos mucho espacio.
La forma de pensarlo es que vamos a leer la secuencia letra por letra y realizar un seguimiento de en qué “estados” podemos estar (al elegir diferentes subsecuencias de lo que leemos). ¿Qué es un “estado”? La idea es que es un grupo (formalmente, clase de equivalencia) de subsecuencias de lo que ya se leyó, desde el cual podemos continuar de la misma manera. Entonces, por ejemplo, las subsecuencias “abcdab” y “ab” están en el mismo “estado”: cualesquiera que sean las letras que agreguemos a la primera, será una secuencia válida si y solo si las mismas letras agregadas a la segunda lo hacen Una secuencia válida.
Primero tenga en cuenta que solo necesitamos considerar subsecuencias que comiencen con un cierto número de ADN Albocede válidos, y luego un ADN Albocede “parcialmente hecho”, y los ya hechos no importan para lo que sigue. Entonces, solo necesitamos saber sobre el último. En particular, necesitamos saber:
- Supongamos que finalmente se comprueba que comer alimentos GM en realidad deja un impacto rastreable en el ADN de una persona. ¿Podría un abogado de propiedad intelectual argumentar que el ADN posterior es la propiedad intelectual de una organización? ¿Tendría derecho un individuo a recuperarse de daños genéticos?
- ¿Cuál es el impacto de los genes / ADN en el carácter de los niños?
- ¿Cuánta información almacena el ADN humano?
- Cuando se alcance la velocidad de escape de la longevidad, ¿podrá un niño de 100 años mirar como lo hizo cuando tenía 20 años?
- Cómo usar el ADN para comprender la respiración aeróbica y la fotosíntesis
1) La última letra.
2a) Si la última letra es ‘a’, cuántas ‘a’ hay en la última secuencia.
2b) Si la última letra es ‘b’, cuántas ‘a’ hay y cuántas ‘b’ hay.
2c) Si la última letra es ‘c’, ¿cuántas ‘c’ más necesitamos y cuántas ‘b’ hay?
2d) Si la última letra es ‘d’ (asumimos que el número de ‘a’s y’ c’s son iguales), ¿cuántas ‘d’s más necesitamos?
Dado que un solo ADN Albocede no puede tener más de 250 de una sola letra, hay 250 estados que terminan en ‘a’, 250 * 250 que terminan en ‘b’, 250 * 250 que terminan en ‘c’ y 250 que terminan en ‘d ‘. Suponga que para algunos K, usted sabe de cuántas maneras puede obtener una subsecuencia que se encuentra en un estado dado, para cualquiera de los estados (para K = 0 es fácil, podemos suponer que hay un ADN de Albocede completo delante de nosotros, por lo que el estado es (‘d’, 0)). Calculemos los números para K + 1.
Entonces, obviamente, podemos ignorar la primera letra de K +, por lo que para cada estado, si podemos acceder a ella en X formas en letras K, podemos llegar a ella en X formas en letras K + 1, ignorando la K + 1ra letra. Además, veamos la última letra.
a) Si es ‘a’, entonces podemos pasar del estado (‘a’, m) a (‘a’, m + 1), entonces, si hubiera X formas de llegar a (‘a’, m) en K letras, tenemos X nuevas formas de llegar a (‘a’, m + 1) en K + 1 letras. Además, podemos llegar de (‘d’, 0) a (‘a’, 1).
b) Si es ‘b’, podemos obtener de (‘b’, m, n) a (‘b’, m, n + 1), y podemos obtener de (‘a’, m) a (‘b ‘, m, 1).
c) Si es ‘c’, podemos obtener de (‘c’, m, n) a (‘c’, m-1, n), y podemos obtener de (‘b’, m, n) a ( ‘c’, m-1, n).
d) Si es ‘d’, podemos pasar de (‘d’, n) a (‘d’, n-1) o de (‘c’, 0, n) a (‘d’, n). [ Actualización: gracias a Tianqi Tang por señalar que me perdí el segundo caso]
Para cada letra, actualizamos como máximo 2 * 250 * 250 estados, por lo que hacemos un total de 500 * 500 * 250 actualizaciones de estado, que serán lo suficientemente rápidas para resolver un solo caso de prueba en menos de un segundo. Puede ver el código de cualquier concursante en el marcador, haciendo clic en ‘Descargar solución’.
