3

動的プログラミングの問題に関するいくつかの指針を探しています。この種の問題を解決する方法に関する関連情報が見つかりません。

問題

 A number is called a special number if it doesn't contain 3 consecutive 
 zeroes. i have to calculate the number of positive integers of exactly d digits 
 that are special answer should be modulo 1000000007(just for overflow in c++).

問題は順列と組み合わせで簡単に解決できますが、動的計画法で解決したいです。最適な下部構造または下から上へのアプローチを見つけることができません。

4

2 に答える 2

1

を最後の桁がゼロであるf(d,x)最上位桁の量とします。ここで、0 ≤ ≤ 2です。 > 1 の場合、再帰があります。dxxd

f(d,0) = (f(d-1,0) + f(d-1,1) + f(d-1,2)) * 9 // f(d,0) は任意の d-ゼロ以外の数字が追加された 1 桁のパターン
f(d,1) = f(d-1,0) // f(d,1) は d-1 桁のパターンから派生し、末尾にゼロが追加されることはありません
f(d,2) = f(d-1,1) // f(d,2) は d-1 桁のパターンに由来し、末尾にゼロが 1 つ追加されます

d= 1 の場合、 がありますf(1,0) = 9, f(1,1) = 0, f(1,2) = 0。

元の問題に対する最終的な答えは ですf(d,0) + f(d,1) + f(d,2)。

デモ用の簡単な C プログラムを次に示します。

#include <cstdio>

const int MOD = 1000000007;
long long f[128][3];

int main() {
  int n;
  scanf("%d",&n);
  f[1][0] = 9;
  for (int i = 2 ; i <= n ; ++i) {
    f[i][0] = (f[i-1][0] + f[i-1][1] + f[i-1][2]) * 9 % MOD;
    f[i][1] = f[i-1][0];
    f[i][2] = f[i-1][1];
  }
  printf("%lld\n", (f[n][0] + f[n][1] + f[n][2]) % MOD);
  return 0;
}
于 2012-07-26T12:46:23.830 に答える
0

注: ロジックを完全にテストしていないので、間違っている可能性がある場所を指摘してください。

問題の再発は、

f(d)=f(d/2)*f(d-d/2)-( f(d/2-1)*f(d-d/2-2) + f(d/2-2)*f(d-d/2-1) ) f(0)=1;f(1)=10;f(2)=100;f(3)=999;

ここで、f(i)は、最初の数字として「0」が発生する可能性があることを考慮して、形成できる特殊数字の総数です。したがって、「d」桁の数字の実際の答えは になります9*f(d-1)。

反復解を簡単にメモして DP 解を作成できます。

このソリューションの有効性を試していないため、間違っている可能性があります。ここに私の論理があります：

の場合、数字をと桁f(d)の数字に分割/分割し、の積を追加します。ここで、作成したパーティション全体で発生する可能性のある無効なケースを削除するために、答えから減算します (作成したパーティション全体で 3 つのゼロが発生すると仮定します)。紙とペンで試してみてください。d/2(d-d/2)f(d)*f(d-d/2)f(d/2-1)*f(d-d/2-2) + f(d/2-2)*f(d-d/2-1)

于 2012-07-22T15:51:16.110 に答える