Problema de Programación Dinámica de Dígitos para la Suma de Números
Quiero encontrar la suma de todos los enteros positivos en el rango [1, N] con una suma de dígitos dada. Por ejemplo, si n = 100 y d = 7, la respuesta será 7 + 16 + 25 + 34 + 43 + 52 + 61 + 70 = 308.
El siguiente código se puede usar para contar los números en el rango [1, N] con una suma de dígitos dada.
cnt[i][0][s] denota la cantidad de sufijos que se pueden formar a partir del índice i, cuya suma de dígitos es s.
cnt[i][1][s] es la cantidad de sufijos que se pueden formar a partir del índice i, cuya suma de dígitos es s, siempre que el sufijo formado no sea mayor que el sufijo correspondiente en la cadena de entrada.
#include <bits stdc++.h="">
using namespace std;
typedef long long int i64;
i64 cnt[20][2][200];
void digit_sum_dp(string ss) {
int n = ss.size();
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 200; k++) {
cnt[i][j][k] = 0;
}
}
}
cnt[n][0][0] = 1;
cnt[n][1][0] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int tight = 0; tight < 2; tight++) {
for (int sum = 0; sum < 200; sum++) {
if (tight) {
for (int d = 0; d <= ss[i] - '0'; d++) {
if (d == ss[i] - '0') {
cnt[i][1][sum] += cnt[i + 1][1][sum - d];
} else {
cnt[i][1][sum] += cnt[i + 1][0][sum - d];
}
}
} else {
for (int d = 0; d < 10; d++) {
cnt[i][0][sum] += cnt[i + 1][0][sum - d];
}
}
}
}
}
return cnt[0][1][d];
}
int main() {
string str = "100";
int d = 7;
cout << digit_sum_dp(str, d) << "\n";
return 0;
}
He intentado ampliar el código para encontrar la suma de los números en lugar de la cantidad de números. A continuación se muestra un fragmento de código.
cnt[i][1][sum] += cnt[i + 1][1][sum - d];
tot[i][1][sum] += (d * cnt[i + 1][1][sum - d] + tot[i + 1][1][sum - d] * pow(10, i));
Obtengo resultados incorrectos para algunos de los datos de entrada. Agradecería si alguien puede ayudarme.
davy.ai
Según el fragmento de código proporcionado, estás intentando modificar el código original para encontrar la suma de los números en lugar de la cantidad. Sin embargo, parece haber un problema con el cálculo de la suma total en el código modificado.
Específicamente, en el bucle interno donde estás iterando sobre los posibles valores de dígitos (
d) para la posición actuali, estás agregando atot[i][1][sum]el producto dedycnt[i + 1][1][sum - d], así como el producto de la suma total en la posicióni+1y una potencia de 10. Mientras que el primer término es correcto (ya que quieres agregarda la suma de todos los posibles sufijos), el segundo término no lo es.El problema es que la suma total en la posición
i+1no es la representación decimal de la suma del sufijo. En cambio, es la suma de todos los posibles sufijos que terminan en el mismo índice que el sufijo actual, y que tienen la misma suma de dígitos que el sufijo actual. Por lo tanto, multiplicar este valor por una potencia de 10 y agregarlo atot[i][1][sum]llevará a la doble contabilización.Para solucionar esto, puedes ajustar el cálculo de la suma total de la siguiente manera:
En este fragmento de código revisado, estamos multiplicando
dpor una potencia de 10 para desplazarlo al lugar decimal correcto, y luego agregando atot[i][1][sum]solo la contribución de la suma del sufijo de los sufijos correspondientes (es decir,d * cnt[i + 1][1][sum - d] * pow(10, i)), en lugar de la contribución de la suma total.Con esta modificación, tu código debería ser capaz de calcular correctamente la suma de todos los números enteros positivos en el rango [1,N] con una suma de dígitos
d.