ural 1009 记忆化搜索

向右看齐 2022-08-09 14:51 180阅读 0赞

## 1009. K-based Numbers ##

Time limit: 1.0 second  
Memory limit: 64 MB

Let’s consider *K*\-based numbers, containing exactly *N* digits. We define a number to be valid if its *K*\-based notation doesn’t contain two successive zeros. For example:

*  1010230 is a valid 7-digit number;
 *  1000198 is not a valid number;
 *  0001235 is not a 7-digit number, it is a 4-digit number.

Given two numbers *N* and *K*, you are to calculate an amount of valid *K* based numbers, containing *N* digits.

You may assume that 2 ≤ *K* ≤ 10; *N* ≥ 2; *N* \+ *K* ≤ 18.

### Input ###

The numbers *N* and *K* in decimal notation separated by the line break.

### Output ###

The result in decimal notation.

### Sample ###

<table> 
 <tbody> 
  <tr> 
   <th>input</th> 
   <th>output</th> 
  </tr> 
  <tr> 
   <td> <pre>2
10
</pre> </td> 
   <td> <pre>90
</pre> </td> 
  </tr> 
 </tbody> 
</table>

**题意：给你一个k进制的数，让你计算出符合条件的n位的k进制的数的个数。条件就是k进制的数不能有连续的两个0，更不能有前导零。**

**分析：直接dfs就行，第一位要从1开始，循环到k-1，每次记录下当前的末尾的数，如果是零，那么下一位就不能取零。纯dfs是能过的400+ms，如果把计算的结果把存下来，就变成了1ms。**

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    const int N=100100;
    
    ll dp[22][22];
    int n,k;
    
    ll dfs(int cnt,int tail)
    {
        if(cnt==n+1) return 1;
        if(dp[cnt][tail] != -1) return dp[cnt][tail];
        ll ret=0;
        int mn=tail==0? 1 : 0;
        for(int i=mn;i<k;i++)
        {
            ret += dfs(cnt+1,i);
        }
        return dp[cnt][tail]=ret;
    }
    
    
    int main()
    {
    
        while(~scanf("%d%d",&n,&k))
        {
            mem(dp,-1);
            printf("%I64d\n",dfs(1,0));
        }
    
        return 0;
    }