FZU_2019_Mountain Numberの問題解

私は頭を垂らします.めまいがします.この問題はついにデジタルDPの本質をはっきり見せてくれた.
http://acm.fzu.edu.cn/problem.php?pid=2109


タイトル

Problem Description



One integer number x is called "Mountain Number" if:



(1) x>0 and x is an integer;



(2) Assume x=a[0]a[1]...a[len-2]a[len-1](0≤a[i]≤9, a[0] is positive). Any a[2i+1] is larger or equal to a[2i] and a[2i+2](if exists).



For example, 111, 132, 893, 7 are "Mountain Number" while 123, 10, 76889 are not "Mountain Number".



Now you are given L and R, how many "Mountain Number" can be found between L and R (inclusive) ?



 Input



The first line of the input contains an integer T (T≤100), indicating the number of test cases.



Then T cases, for any case, only two integers L and R (1≤L≤R≤1,000,000,000).



 Output



For each test case, output the number of "Mountain Number" between L and R in a single line.

 Sample Input



3

1 10

1 100

1 1000

 Sample Output



9

54

384

标题:ペア区間[l,r]をあげて、区間内のMountain数の個数を閉じさせていただきます.
Mountain数の定義:a 0 a 1 a 2 a 3をあげる...an,aiは現在のビットの数を表し,いずれかの奇数ビットの数が隣の偶数ビットの数よりも大きい,これがMountain数である.
作り方:デジタルdpの記憶化検索
まず、dp配列が何に使われているのかを理解します.実は現在の数桁の状態(この状態は通常前の数桁と関係がある)を記録してどれだけの適合を出すことができるか、つまりdp配列は前啓後を受けており、記憶化探索の本質は再帰解樹であり、この大木が根から葉ノードまでどれだけの適合経路を見つけることができるかを求める.dp配列が3次元であれば、dpと定義する[a][b][c].,記憶化探索の時間的複雑度はO(a*b*c)である.
本題では,dp配列をdp[pos][pre][parity]と定義し,posは現在の位置を表し,preは上位の数字を表し,parityはプリアンブル0のない数字から次の状態ビットへのパリティ(数字はa 0から始まることに注意),奇数は1,偶数は0を表す.
DFS関数の構築を開始します.
一、パラメータを確定する:
1、まず万年不変のposで、現在どちらを計算するかを表します
2、それから普通のpreを探して、前の数字を代表します
3、parity、プリアンブル0なしから次の状態へのパリティ
4、jud、先頭0のない数位を計算したかどうか、
5、doing、上界に着くかどうか
二、関数構造化の書き方
1、万年不変、if(pos=-1){どのように垂らします}//return 1ではありませんて0です
2、万年不変:if(!doing&&&dp[][]!=-1)return dp[][];
3、境界endを確定する
4、for(i=0;i<=end;++i)、条件を満たす場合、ans+=dfs()
5、現在前回に到達していない場合はansの値をdpに割り当てる[][][]
6、return ans
三、いつansがdfs()を加えた状態で一致数の個数を必要とするのか
1、現在位置がまだプリアンブル0の場合、追加する必要がありますが、preを9と定義することを忘れないでください.これにより、プリアンブル0以外の数桁に遭遇した場合、エラーは判断されません.
2、現在位置はもう前列0ではありません(前に0以外の数字があります)、現在位置は奇性で、次の位置は余剰という位置の数字に等しいか、または小さいです.
3、現在位置はもう前列0ではありません(前に0以外の数字があります)、現在位置は偶数で、次の位置はこの位置の数字に等しいかそれ以上です.
そして個人的にはcal関数は言うに値しないと思い、詳しくは書きません.

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int dp[12][10][2],digit[12];

int dfs(int pos , int pre,int parity,bool jud,bool doing) //doing   ，pos         

{

  if(pos==-1) return 1;

  if(!doing&&dp[pos][pre][parity]!=-1)

      return dp[pos][pre][parity];

  int ans=0,end;

  end=doing?digit[pos]:9;

  for(int i=0;i<=end;++i)

  {

      /*

      jud        0,pre     9 ，             0    ，

            。   parity=0,    pre>=i，

      */

      if(!(jud||i)) ans+=dfs(pos-1,9,0,jud||i,doing&&i==end); //         0

      else if(parity&&pre<=i)  //          

          ans+=dfs(pos-1,i,parity^1,jud||i,doing&&i==end);

      else if(!parity&&pre>=i) //          

          ans+=dfs(pos-1,i,parity^1,jud||i,doing&&i==end);

  }

  if(!doing)

      dp[pos][pre][parity]=ans;

  return ans;

}

int cal(int x)

{

    int pos = 0;

    while(x)

    {

        digit[pos++] = x % 10;

        x /= 10;

    }

    return dfs(pos-1,9,0,0,1); //9   ~~

}

int main()

{

    int t,l,r;

    cin>>t;

    memset(dp,-1,sizeof(dp));

    while(t--)

    {

        cin>>l>>r;

        printf("%d
",cal(r)-cal(l-1));

    }

}