-5

当我针对这个问题在 spoj 上提交 dp 问题的解决方案时，我总是遇到段错误。但我的解决方案适用于其他平台，如 Visual Studio 和 Ideone。我不知道为什么我会收到这个错误，你能帮忙吗？

我的代码：

#include <iostream>
#include <cmath>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <vector>
#include <cstring>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <set>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <climits>
#include <cctype>
#include <bitset>
#include <numeric>
#include <array>
#include <tuple>
#include <stdexcept>
#include <utility>
#include <functional>
#include <locale>

#define mp make_pair
#define pb push_back
#define IO ios_base::sync_with_stdio(0);    cin.tie(0); cout.tie(0);
#define sz size()
#define len length()
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
#define all(v) ((v).begin()), ((v).end())
#define mms(Arr, Value) memset(Arr, Value, sizeof(Arr))
#define printl(ans) cout << ans << endl
#define vpii vector<pair<int, int> >
#define vpll vector<pair<ll, ll> >
#define pll pair<ll, ll>
#define re return
#define fri(x,n)    for(int i = x ; i < n ; ++i)
#define frj(x,n)    for(int j = x ; j < n ; ++j)
typedef long long int ll;

const int oo = INT_MAX;
const ll OO = 1e18;

using namespace std;

ll GCD(ll a, ll b) { return((!b) ? a : GCD(b, a % b)); }
ll LCM(ll a, ll b) { return a / (GCD(a, b)) * b; }
bool isPrime(ll n) {
    if (n == 2)re 1;
    if (n < 2 || n % 2 == 0)re 0;
    for (ll i = 3; i * i <= n; i += 2)
        if (n % i == 0)re 0;
    re 1;
}



// take it as string
string a, b;
int ar[11];
ll dp[11][100][2];                // if max input is 1e9, so max pos is 10 and max sum of a one number is 9*9.. did not put a dimension for n as it is constant for all states

ll fun(int pos, ll sum, int flag, int n) {

    if (pos > n) re dp[pos][sum][flag] = sum;

    if (dp[pos][sum][flag] != -1) re dp[pos][sum][flag];

    // if flag is 0 then this state is limited by ar[pos] value. 

    int limit = 9;
    if (flag == 0) limit = ar[pos];

    // determine next state: put next flag not limited (1) when curr flag is not limited (1) OR i is still under (smaller than) limit
    // put next flag limited (0) when curr flag is limited AND i equals the limit .. you can NOT put OR as : the flag of curr state may be limited but the next state 
    // would be limited only if i==limit, as if i<limit the next state is always free whether flag is 1 or 0. 
    // if i==limit, the next state would only be limited if flag is 0. as if curr flag was free so limit of curr state was 9 and now i is 9, the next state can not be limited because flag is 1 even if i==limit.. so you must put them both !flag ,  i==limit and you must put AND


    ll res = 0;
    fri(0, limit + 1) {

        if (!flag && i == limit)
            res += fun(pos + 1, sum + i, 0, n);  // limited
        else
            res += fun(pos + 1, sum + i, 1, n); // free
    }

    re dp[pos][sum][flag] = res;
}

int NumDigitSum(string s) {
    // takes the num as string and return the sum of its digits
    int sum = 0;
    fri(0, s.sz) {
        sum += s[i] - '0';
    }

    re sum;
}



int main() {
    IO;
    cin >> a >> b;

    while (a != "-1") {


        mms(dp, -1);
        // ar is one indexed
        fri(1, a.sz + 1) {
            ar[i] = a[i - 1] - '0';   // convert to int
        }
        ll aans = fun(1, 0, 0, a.sz);


        mms(dp, -1);
        // ar is one indexed
        fri(1, b.sz + 1) {
            ar[i] = b[i - 1] - '0';   // convert to int
        }
        ll bans = fun(1, 0, 0, b.sz);

        cout << bans - aans + NumDigitSum(a) << endl;
        cin >> a >> b;
    }

    return 0;
}
4

1 回答 1

3

好吧，这种用勺子喂食是非常不鼓励的，但我来了：

#include <iostream>
#include <string>

//number of headers = 3

//no use of using namespace std;

int main() {
    int n = 100;
    long sum = 0;
    for (int i = 1; i <= n; i++) {
        std::string num_as_string = std::to_string(i);
        for(const auto& digit_as_char : num_as_string) {
            sum = sum + digit_as_char - '0';
        }
    }
    std::cout << sum;
    return 0;
}

注意代码中的一些内容：

  • 它简短而简洁
  • 它使用标准字符串库来分隔数字，这比自定义逻辑要好得多
  • 它的可读性很强，不会让任何人紧张
于 2020-08-10T15:28:35.020 回答