欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

数位dp相关例题

程序员文章站 2022-03-11 16:10:13
1.不要62题目链接题解:代码:#include #include #include #include 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;...

1.不要62
题目链接

数位dp相关例题

代码:

#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.数字游戏
题目链接
数位dp相关例题

代码:

#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.数字游戏
题目链接
数位dp相关例题

代码:

#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));
    }
     

}

本文地址:https://blog.csdn.net/jahup/article/details/109146125