Bueno, nuestro equipo lo resolvió formulando el estado dp como:
dp [i] [j] = Peso total máximo que puede obtener cuando está en ith ronda y gastando j cantidad de precio.
Luego, puede simplemente inicializar su tabla dp como vacía e ir iterativamente.
Entonces el caso base resulta ser dp [1] [costo del primer (0º) elemento] = peso del primer (0º) elemento
Para cada artículo, calcula valores para cada costo que puede obtener (que para esta pregunta fue el más bajo = 0 y el más alto = 100 * 10).
Ahora hay dos cosas:
- ¿Es posible expandir [matemáticas] (a + b) ^ {\ frac {1} {2}} [/ matemáticas]?
- ¿De cuántas maneras podemos pedir una docena de conos de helado de 31 sabores si se puede pedir un sabor no más de 10 veces?
- ¿Cuál es la proporción áurea?
- ¿Cómo encontrar las intersecciones - e y de la función de sincronización (sinx / x)? ¿Cómo lo trazo a mano?
- ¿Por qué son importantes los subgrupos normales?
- ¿Necesitamos incluir este peso en el conjunto?
- Si incluimos este peso en el conjunto, ¿cómo afecta el ans para el próximo peso en la lista?
Ahora para responder al primer punto:
Por cada costo en el que estamos actualmente, simplemente podemos verificar:
- Primero, si hemos calculado alguna respuesta para ello.
- En caso afirmativo, podemos verificar si el peso que tenemos es mayor o igual al peso requerido (ese es el peso actual en cuestión.
- Si tenemos el peso que tenemos actualmente, hemos ganado esta ronda y podemos actualizar los ans para el próximo peso.
Para el segundo punto:
- Si incluimos el peso actual en el conjunto actual, entonces el nuevo costo es (j + costo del i-ésimo peso) y el peso actual en el conjunto es (dp [i] [j] + peso del i-ésimo elemento)
- Ahora podemos simplemente comparar este valor con el valor para el siguiente peso, es decir, podemos hacer esto
dp [elemento siguiente] [j + costo del elemento actual] = max (dp [elemento siguiente] [j + costo del elemento actual], dp [elemento actual] [j] + peso del elemento actual)
Ahora simplemente calculamos esta tabla para todos los elementos. La complejidad del algoritmo resulta ser O (N * 1000). Se nos pregunta el precio mínimo necesario para ganar. Así que al final encontramos el min j tal que dp [N] [j] está definido.
Espero que esté claro ahora. Aquí está nuestra presentación:
Solución | CodeChef
