首页 > 其他分享 >数位dp例题

数位dp例题

时间:2022-11-05 15:24:09浏览次数:91  
标签:10 例题 int xx vec include dp 数位

怎么感觉这种dp有点过于板子

 

1. 某人命名了一种不降数,这种数字必须满足从左到右各位数字成小于等于的关系,如12245

  问区间【l,r】内有多少个不降数。

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
 vector<int> vec;
 int f[40][40][2];
 int xx,yy;
 int dp(int len,int x,int fg){
     if(len<0) return 1;
     if(f[len][x][fg]!=-1) return f[len][x][fg];
     int t=0;
     int end=(fg?vec[len]:9);
     
     for(int i=x;i<=end;i++){
         t+=dp(len-1,i,fg&&i==end);
     }
     if(fg==0) f[len][x][fg]=t;
     return t;
 }
 int solve(int x){
     memset(f,-1,sizeof f);
     vec.clear();
     while(x>0){
         vec.push_back(x%10);
         x/=10;
     }
     return dp(vec.size()-1,0,1);
 }
 int main(){
     while(cin>>xx>>yy){
         cout<<solve(yy)-solve(xx-1)<<endl;
     }
 }

 

2.

Windy 数:不含前导零且相邻两个数字之差至少为2 的正整数被称为 Windy 数。

求[L,R] 共有多少个 Windy 数

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
 vector<int> vec;
 int f[40][40][2];
 int xx,yy;
 
 int dp(int len,int x,int fg){
     if(len<0) return 1;
     if(f[len][x][fg]!=-1) return f[len][x][fg];
     int t=0;
     int end=(fg?vec[len]:9);
     
     for(int i=0;i<=end;i++){
         if(abs(i-x)<2) continue;
         
         if(x==11&&i==0) 
         t+=dp(len-1,11,fg&&i==end);
         else 
         t+=dp(len-1,i,fg&&i==end);
     }
     if(fg==0) f[len][x][fg]=t;
     return t;
 }
 int solve(int x){
     vec.clear();
     while(x>0){
         vec.push_back(x%10);
         x/=10;
     }
     return dp(vec.size()-1,11,1);
 }
 int main(){
     memset(f,-1,sizeof f);
     cin>>xx>>yy;
         cout<<solve(yy)-solve(xx-1)<<endl;
 }

 

3. 不吉利的数字: 数字中含有 4 或 62。 问这种数字 [L,R] 中有多少?

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
 vector<int> vec;
 int f[40][40][2];
 int xx,yy;
 
 int dp(int len,int x,int fg){
     if(len<0) return 1;
     if(f[len][x][fg]!=-1) return f[len][x][fg];
     int t=0;
     int end=(fg?vec[len]:9);
     
     for(int i=0;i<=end;i++){         
         if(i==4||(i==2&&x==6)) continue;
         t+=dp(len-1,i,fg&&i==end);
     }
      f[len][x][fg]=t;
     return t;
 }
 int solve(int x){
     vec.clear();
     memset(f,-1,sizeof f);
     while(x>0){
         vec.push_back(x%10);
         x/=10;
     }
     return dp(vec.size()-1,0,1);
 }
 int main(){
     while(cin>>xx>>yy,xx)
         cout<<solve(yy)-solve(xx-1)<<endl;
 }

 

4.

,求在 [l,r] 中的所有整数中,每个数码各出现了多少次

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 #define int long long
 vector<int> vec;
 int f[30][30][30][2];
 int xx,yy;
 int number;
 
 int dp(int len,int x,int s,int fg){
     if(len<0) return s;
     if(f[len][x][s][fg]!=-1) return f[len][x][s][fg];
     int t=0;
     int end=(fg?vec[len]:9);
     
     for(int i=0;i<=end;i++){     
           if(i==0&&x==11){
               t+=dp(len-1,11,s,fg&&i==end);
           }
           else t+=dp(len-1,i,s+(i==number),fg&&i==end);
     }
      f[len][x][s][fg]=t;
     return t;
 }
 int solve(int x){
     vec.clear();
     memset(f,-1,sizeof f);
     while(x>0){
         vec.push_back(x%10);
         x/=10;
     }
     return dp(vec.size()-1,11,0,1);
 }
  main(){
    cin>>xx>>yy;
         for(number=0;number<=9;number++)
          cout<<solve(yy)-solve(xx-1)<<' ';
          cout<<endl;
 }

 

标签:10,例题,int,xx,vec,include,dp,数位
From: https://www.cnblogs.com/towboa/p/16860251.html

相关文章

  • 腾讯云Linux轻量服务器使用宝塔面板一键部署WordPress个人博客教程
    WordPress作为动态博客的代表,至今已经有十几年历史,而且一直在更新发展中,功能强大,插件和主题丰富,WordPress搭建使用也很方便。作为个人站长和博主,很多都是从WordPress入门......
  • Android实现UDP通信
    TCP和UDP的不同上次我们讲的是TCP的socket,他们之间的不同在于,tcp要等待客户端的接入,然后获得客户端socket然后进行IO操作,udp直接传送数据即可  图片来源:面试官:说说U......
  • Solution-P7650 [BalticOI 2007 Day 1] Ranklist Sorting(DP)
    容易发现一条性质:每个人最多只会被移动一次。说明人只有两种:移动的和不移动的。考虑枚举所有不移动的人,并最优化其它人的移动顺序。最开始第\(i\)个人的起点为\(i\),终......
  • 深入浅出DPDK 电子书 pdf
    作者:朱河清/梁存铭/胡雪焜出版社:机械工业出版社 链接:深入浅出DPDK  近年来,随着网络技术的不断创新和市场的发展,越来越多的网络设备基础架构开始向基于通......
  • EasyCVR国标GB28181协议接入下的TCP和UDP模式说明及差异
    有用户在使用我们的平台时,经常会出现对于端口的疑问,同时也不了解端口的差别。今天我们来解释说明下EasyCVR平台关于国标GB28181协议接入下的TCP和UDP模式的说明及差异。......
  • 基于 Docker 构建轻量级 CI 系统:Gitea 与 Woodpecker CI 集成
    WoodpeckerCI是一个由社区维护的DroneCI分支,使用ApacheLicense2.0许可证发布。社区版进一步扩展了pipeline的功能特性、支持对文件路径设置pipeline执行条件,并......
  • UDP、TCP
    /**UDP协议:*1.面向无连接,不可靠协议*2.数据会被分包,数据限制在64k*3.不需要建立连接,速度快*比如:聊天数据共享,视频会议时数据传输.*TCP协议:*1.必须建......
  • D. Bishwock_线性dp
    D.Bishwock一万年没写题解了,俺又回来了题目大意给2*n的地图,有若干个格子不能放东西,问最多可以放入几个“L”形的棋子。思路基础线性dp,设dpi为前i个的最多情况。然后......
  • P1103 书本整理 (DP)
    书本整理题目描述Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架,想要把书放在书架上。书架可以放下所有的书,所以Frank首先将书按高度顺序排列在书架上。但是Frank......
  • ThreadPoolExecutor 源码解析
    Java中的线程池是运用场景最多的并发框架,几乎所有需要异步或并发执行任务的程序都可以使用线程池。合理地使用线程池能够带来3个好处:降低资源消耗。通过重复利用已创建的线......