数位dp相关例题

1.不要62
题目链接

代码:

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
int dp[20][2];
int a[20];
int dfs(int pos, int pre, int sta, bool limit)
{
     if (pos == -1)
          return 1;
     if (!limit && dp[pos][sta] != -1)
          return dp[pos][sta];

     int up = limit ? a[pos] : 9;
     int ans = 0;
     for (int i = 0; i <= up; i++)
     {
          if (pre == 6 && i == 2)
               continue;
          if (i == 4)
               continue; //都是保证枚举合法性
          ans += dfs(pos - 1, i, i == 6, limit && i == a[pos]);
     }
     return ans;
}

int solve(int x)
{

     int pos = 0;
     while (x)
     {
          a[pos++] = x % 10;
          x /= 10;
     }
     return dfs(pos - 1, 0, 0, true);
}

int main()
{
     int n, m;
     while (cin >> n >> m)
     {
          memset(dp, -1, sizeof(dp)); //0也是合法状态
          if (n == 0 && m == 0)
               break;

          cout << solve(m) - solve(n - 1) << endl;
     }

     return 0;
}

2.数字游戏
题目链接

代码:

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int a[40];
int f[40][15];

int dfs(int x, int pre, bool limit)
{
     if (x == -1)
          return 1;
     if (!limit && f[x][pre] != -1)
          return f[x][pre];
     int up;

     up = limit ? a[x] : 9;

     int res = 0;
     for (int i = 0; i <= up; i++)
     {
          if (i >= pre)
               res += dfs(x - 1, i, i == up && limit);
     }
     if (!limit)
          f[x][pre] = res;
     return res;
}

int solve(int x)
{
     memset(f, -1, sizeof(f));
     int pos = 0;
     while (x)
     {
          a[pos++] = x % 10;
          x /= 10;
     }
     return dfs(pos - 1, 0, true);
}

int main()
{
     int x, y;

     while (cin >> x >> y)
     {
          cout << solve(y) - solve(x - 1) << endl;

          return 0;
     }
}

3.数字游戏
题目链接

代码:

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int a[20];
int dp[20][105];
int x, y,mod;

int dfs(int pos,int sum,bool limit)
{    
     if(pos<0) return sum==0;
     if(!limit&&dp[pos][sum]!=-1) return dp[pos][sum];

     int up=limit?a[pos]:9;
     int ans=0;
     for(int i=0;i<=up;i++)
     {    

          ans+=dfs(pos-1,(sum+i)%mod,limit&&i==up);
     }
     return dp[pos][sum]=ans;

}

int solve(int x)
{
     
     int pos = 0;
     memset(dp,-1,sizeof(dp));
     while (x)
     {
          a[pos++] = x % 10;
          x /= 10;
     }
     return dfs(pos-1,0, true);
      
}

int main()
{
     
     while(scanf("%d%d%d",&x,&y,&mod)!=EOF)
    {
        memset(dp,-1,sizeof(dp));
        printf("%d\n",solve(y)-solve(x-1));
    }
     

}