首页 > 代码库 > BNU52325-Increasing or Decreasing-数位DP-DFS

BNU52325-Increasing or Decreasing-数位DP-DFS

2024-08-16 19:36:31   210人阅读

题目地址：  https://www.bnuoj.com/v3/problem_show.php?pid=52325

两份代码，解释在第二份代码里面

第一份代码整理一下看着爽

技术分享
 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 long long  dp[20][11][3]; 6 int digit[20]; 7 int dfs(int len , int fore , int state , bool limit) 8 { 9     if (len == 0)10         return 1;11     if ( !limit && dp[len][fore][state] != -1 )12         return dp[len][fore][state];13     int res = 0;14     int limitD = limit ? digit[len] : 9 ;15     for (int j = 0 ; j<=limitD; j++)16     {17         int i;18         if (fore == 10 && j == 0) i = 10;19         else i = j;20         if ( state == 0 ){21             if ( fore == 10 || i == fore )22                 res += dfs( len - 1 , i , 0 , limit && i == limitD );23         }24         else if ( state == 1 ){25             if ( fore == 10 || i <= fore )26                 res += dfs( len - 1 , i , 1 , limit && i == limitD );27         }28         else{29             if ( fore == 10 || i >= fore )30                 res += dfs( len - 1 , i , 2 , limit && i == limitD );31         }32     }33     if (!limit)34         dp[len][fore][state] = res;35     return res;36 }37 long long solve(long long x)38 {39     int cnt = 0;40     while (x)41     {42        digit[ ++cnt ] = ( int )( x % 10LL );43        x /= 10LL;44     }45     return dfs( cnt , 10 , 1 , true ) + dfs( cnt , 10 , 2 , true ) - dfs( cnt , 10 , 0 , true );46 }47 int main()48 {49     memset(dp,-1,sizeof dp);50     int N;51     scanf("%d", &N );52     long long  a,b;53     while (N--)54     {55         scanf("%lld %lld" , &a , &b );56         printf("%lld\n", solve( b ) - solve ( a - 1LL ) );57     }58 }
View Code

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 //dp[i][j][k] 长度为i,前一位j,状态为k 6 //k=0 相等 k=1 递增 k=2 递减 7 long long  dp[20][11][3]; 8 int digit[20]; 9 //dfs计算在digit限制下，长度为len，前一位为fore，的state状态的数字，特别的令fore==10代表前面全是010 int dfs(int len , int fore , int state , bool limit)11 {12     //最边界计数，即枚举到最后一位，0即为全是前导0。13     if (len == 0)14     {15         return 1;16     }17     //记忆化搜索18     if (!limit && dp[len][fore][state] != -1)19      return dp[len][fore][state];20     int res = 0;21     int limitD = limit?digit[len]:9;22     for (int j = 0 ; j<=limitD; j++)23     {24         int i;25         //确定填写的0,前导0变10,真0还是026         if (fore == 10 && j == 0) i = 10;27         else i = j;28         //如果前导0或者满足要求，那么继续dfs29         //其中有些判断可以省略，但是所有的都加上fore==10,便于理解30         if (state==0)      //相等31         {32                     if (fore==10||i==fore)33                     res += dfs(len-1,i,0,limit&&i==limitD);34         }35         else if (state==1)//递减36         {37                     if (fore==10||i<=fore)38                     res += dfs(len-1,i,1,limit&&i==limitD);39          }40          else           //递增41          {42                     if (fore==10||i>=fore)43                     res += dfs(len-1,i,2,limit&&i==limitD);44          }45     }46     if (!limit) dp[len][fore][state] = res;47     return res;48 }49 long long solve(long long x)50 {51     int cnt = 0;52     while (x)53     {54        digit[++cnt] = (int)(x % 10LL);55        x /= 10LL;56     }57     //递增+递减-相等58     return dfs(cnt,10,1,true) + dfs(cnt,10,2,true) - dfs(cnt,10,0,true);59 }60 int main()61 {62     memset(dp,-1,sizeof dp);63     int N;64     scanf("%d",&N);65     long long  a,b;66     while (N--)67     {68         scanf("%lld%lld",&a,&b);69         printf("%lld\n",solve(b) - solve(a-1LL) );70     }71 }

 

BNU52325-Increasing or Decreasing-数位DP-DFS


联系
我们