C++ を使用して、K 進木で重み W を持つパスの数を求めます。-C++-php.cn

C++ を使用して、K 進木で重み W を持つパスの数を求めます。

WBOY

リリース： 2023-09-16 18:09:04

転載

736 人が閲覧しました

C++ を使用して、K 進木で重み W を持つパスの数を求めます。

この記事では、C を使用して、K 進木内の重み W を持つパスの数を数えます。 K 進木が与えられました。これは、各ノードが K 個の子を持ち、各エッジが重みを持ち、ノードからそのすべての子に向かって重みが 1 から K に減少する木です。

ルートノードから始まり、重み W を持つパスと重み M を持つ少なくとも 1 つのエッジの累積数をカウントする必要があります。ここに例を示します:

Input : W = 4, K = 3, M = 2

Output : 6

ログイン後にコピー

与えられた問題では、時間と空間の複雑さを軽減するために dp を使用します。メモ化を使用すると、プログラムを高速化し、より大きな制約に適応させることができます。

メソッド

このメソッドでは、ツリーを走査し、少なくとも M の重みと W に等しい重みの有無にかかわらずエッジを追跡し、その後、答えをインクリメントします。

Input

#include <bits/stdc++.h>
using namespace std;
int solve(int DP[][2], int W, int K, int M, int used){
   if (W < 0) // if W becomes less than 0 then return 0
       return 0;
    if (W == 0) {
        if (used) // if used is not zero then return 1
           return 1; //as at least one edge of weight M is included
       return 0;
   }
    if (DP[W][used] != -1) // if DP[W][used] is not -1 so that means it has been visited.
       return DP[W][used];
    int answer = 0;
   for (int i = 1; i <= K; i++) {
        if (i >= M)
           answer += solve(DP, W - i, K, M, used | 1); // if the condition is true
                                                    //then we will change used to 1.
       else
           answer += solve(DP, W - i, K, M, used);
   }
   return answer;
}
int main(){
   int W = 3; // weight.
   int K = 3; // the number of children a node has.
   int M = 2; // we need to include an edge with weight at least 2.
   int DP[W + 1][2]; // the DP array which will
   memset(DP, -1, sizeof(DP)); // initializing the array with -1 value
   cout << solve(DP, W, K, M, 0) << "\n";
   return 0;
}

ログイン後にコピー