1

我想用给定的数字和 d 找到范围 [1, N] 中所有正整数的总和。例如，如果 n = 100 且 d = 7，则答案将是 7 + 16 + 25 + 34 + 43 + 52 + 61 + 70 = 308。

以下代码可用于用给定的数字总和 d 计算 [1, N] 范围内的数字。

cnt[i][0][s] 表示可以从索引 i 开始形成的后缀的数量，其数字加起来为 s。

cnt[i][1][s] 从索引 i 开始可以形成的后缀计数，其数字加起来为 s，使得形成的后缀不大于输入字符串中的相应后缀

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

我试图扩展代码以找出数字的总和而不是数字的计数。以下是代码片段。

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));

对于某些输入，我得到了不正确的结果。如果有人可以帮助我，我将不胜感激。

4

0 回答 0