怎么感觉这种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