C++でアレイを復元する

配列Aの配列要素を出力するために使用されるプログラムがありますが、プログラムに少し間違いがあったとします。そのプログラムでは、各要素の後に空白がありませんでした。したがって、印刷された文字列が1つある場合、配列を再生成できますか？配列要素が1からkの範囲にあることがわかっています。

文字列sと整数kが与えられます。アレイを復元できる方法がいくつあるかを見つける必要があります。答えは非常に大きい可能性があるため、10 ^ 9+7を法として返します。

したがって、入力がS ="1318"、k =2000の場合、[1318]、[131,8]、[13,18]、[1,318のような8つの異なる配列を形成できるため、出力は8になります。 ]、[1,3,18]、[1,31,8]、[13,1,8]、[1,3,1,8]

これを解決するには、次の手順に従います-

• const int m =1e9 + 7

• 1つのマップdpを定義する

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m））mod m

• 関数help（）を定義します。これには、idx、s、num、k、

  が必要です。

• idx> =sのサイズの場合、-

  • 1を返す

• idxがdpにあり、numがdp [idx]にある場合、-

  • dp [idx、num]

    を返します

• ret：=0

• num>=1かつnum>=kであり、s[idx]が'0'と等しくない場合、-

  • ret：=add（help（idx、s、0、k）、ret）

• num * 10 +（s [idx]-'0'）<=kの場合、-

  • ret：=add（help（idx + 1、s、num * 10 +（s [idx] --ASCII of '0'）、k）、ret）

• dp [idx、num]：=ret

• retを返す

• メインの方法から、次のようにします-

• n：=sのサイズ

• サイズn+1の配列ansを定義します

• ans [0]：=1

• s：=sの前に1つの空白を連結します

• ks：=kを文字列に変換

• 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、実行-

  • cnt：=1

  • temp：=空白の文字列

  • 初期化j：=iの場合、j>=1かつcnt<=10の場合、更新（jを1減らす）、（cntを1増やす）、do-

    • temp：=s [j] + temp

    • s[j]が'0'と同じ場合、-

      • 次の部分を無視し、次の反復にスキップします

    • tempのサイズ>ksのサイズの場合、-

      • ループから出てきます

    • val：=temp as number

    • val>=1かつval<=kの場合、-

      • ans [i]：=add（ans [i]、ans [j-1]）

• ans [n]

  を返します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
   public:
   unordered_map<int, unordered_map<lli, int> > dp;
   lli add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   int help(int idx, string& s, lli num, int k){
      if (idx >= s.size())
      return 1;
      if (dp.count(idx) && dp[idx].count(num))
      return dp[idx][num];
      int ret = 0;
      if (num >= 1 && num <= k && s[idx] != '0') {
         ret = add(help(idx, s, 0, k), ret);
      }
      if (num * 10 + (s[idx] - '0') <= k) {
         ret = add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k),
         ret);
      }
      return dp[idx][num] = ret;
   }
   int numberOfArrays(string s, int k){
      int n = s.size();
      vector<lli> ans(n + 1);
      ans[0] = 1;
      s = " " + s;
      string ks = to_string(k);
      for (lli i = 1; i <= n; i++) {
         lli cnt = 1;
         string temp = "";
         for (lli j = i; j >= 1 && cnt <= 10; j--, cnt++) {
            temp = s[j] + temp;
            if (s[j] == '0')
               continue;
            if (temp.size() > ks.size())
            break;
            lli val = stol(temp);
            if (val >= 1 && val <= k) {
               ans[i] = add(ans[i], ans[j - 1]);
            }
         }
      }
      return ans[n];
   }
};
main(){
   Solution ob;
   cout << (ob.numberOfArrays("1318",2000));
}

入力

"1318", 2000

出力

8