【动态规划】数位dp
典中典 P2602 数字计数
递推实现
首先计算0000…~9999…之间数字出现次数
-
递推角度dp[i]=dp[i−1]×10+10i−1,dp[i]是i位数的计数dp[i]=dp[i-1]\times10+10^{i-1},dp[i]是i位数的计数dp[i]=dp[i−1]×10+10i−1,dp[i]是i位数的计数
- 10i−110^{i-1}10i−1是最高位上出现次数
- dp[i−1]×10dp[i-1]\times 10dp[i−1]×10是其他低位上出现次数
-
排列组合角度dp[i]=i×10i/10dp[i]=i\times 10^i/10dp[i]=i×10i/10
- i个0递增到i个9 所有字符出现i×10ii\times 10^ii×10i
- 再/10/10/10分配到每个数字上
然后分普通情况和逼近情况计算0~x的计数，使用前缀和
const int N=16,INF=1e9+10;
int cnta[10],cntb[10];
int dp[N],ten[N];
void init(){//000...~999...ten[0]=1;forr(i,1,N-1){dp[i]=i*ten[i-1];ten[i]=ten[i-1]*10;}
}
void calc(int x,int *cnt){int len=0;vector<int>num(15,0);while (x){num[++len]=x%10;x/=10;}reforr(i,1,len){//从高到低位 假设为324//普通情况forr(j,0,9)cnt[j]+=num[i]*dp[i-1];// 0~299 后两位 0 1...num[i]-1forr(j,0,num[i]-1)cnt[j]+=ten[i-1];// 0~299 高位 //逼近情况int tp=0;forr(j,1,i-1)tp+=num[j]*ten[j-1];cnt[num[i]]+=(tp+1); //300~324 0~tp 共tp+1//去除前导零cnt[0]-=ten[i-1];}}
void solve()
{init();int a,b;cin>>a>>b;calc(a-1,cnta),calc(b,cntb);forr(i,0,9)cout<<cntb[i]-cnta[i]<<' ';
}
记忆化搜索实现
const int N=16,INF=1e9+10;
int dp[N][N][2][2];
int now,num[N];
/*
pos:从高到低 处理到几位数字
sum:前面now的个数
lead:有无前导零
limit:有无数位限制
*/
int dfs(int pos,int sum,bool lead,bool limit){int ans=0;if(pos==0)return sum;if(dp[pos][sum][lead][limit]!=-1)return dp[pos][sum][lead][limit];int up=(limit?num[pos]:9);forr(i,0,up){//决定这一位是什么数if(i==0&&lead)ans+=dfs(pos-1,sum,1,limit&&i==up);else if(i!=now)ans+=dfs(pos-1,sum,0,limit&&i==up);//没有前导零else if(i==now)ans+=dfs(pos-1,sum+1,0,limit&&i==up);}dp[pos][sum][lead][limit]=ans;return ans;
}
int calc(int x){int len=0;while (x){num[++len]=x%10;x/=10;}memset(dp,-1,sizeof dp);return dfs(len,0,1,1);//lead=true出0就是前导零了 limit&&k->k
}
void solve()
{int a,b;cin>>a>>b;forr(i,0,9)now=i,cout<<calc(b)-calc(a-1)<<' ';
}
P2657 Windy数
const int N=16,INF=1e9+10;
int dp[N][N][2][2];
int now,num[N];/*
pos:从高到低 处理到几位数字
lst:最后一个数
lead:有无前导零
limit:有无数位限制
*/
int dfs(int pos,int lst,bool lead,bool limit){int ans=0;if(pos==0)return 1;if(dp[pos][lst][lead][limit]!=-1)return dp[pos][lst][lead][limit];int up=(limit?num[pos]:9);forr(i,0,up){//决定这一位是什么数if(abs(i-lst)<2)continue;if(i==0&&lead)ans+=dfs(pos-1,-2,1,limit&&i==up);//有前导零else ans+=dfs(pos-1,i,0,limit&&i==up);//没有前导零}dp[pos][lst][lead][limit]=ans;return ans;
}
int calc(int x){int len=0;while (x){num[++len]=x%10;x/=10;}memset(dp,-1,sizeof dp);return dfs(len,-2,1,1);//-2是为了让最高位是任意数 lead=true出0就是前导零了 limit&&k->k
}
void solve()
{int a,b;cin>>a>>b;cout<<calc(b)-calc(a-1)<<endl;
}
P4124 手机号码
const int N=16,INF=1e9+10;
int dp[N][N][N][2][2][2][2];
int num[N];/*
pos:从高到低 处理到几位数字
sec:倒数第二个数 lst:最后一个数 state:是否出现三连
et:8 fr:4
(不用考虑前导零)
limit:有无数位限制
*/
int dfs(int pos,int sec,int lst,bool state,bool et,bool fr,bool limit){int ans=0;if(et&&fr)return 0;if(pos==0)return state;if(dp[pos][sec][lst][state][et][fr][limit]!=-1)return dp[pos][sec][lst][state][et][fr][limit];int up=(limit?num[pos]:9);forr(i,0,up){//决定这一位是什么数ans+=dfs(pos-1,lst,i,state||(i==lst&&i==sec),et||(i==8),fr||(i==4),limit&&i==up);}dp[pos][sec][lst][state][et][fr][limit]=ans;return ans;
}
int calc(int x){int len=0;while (x){num[++len]=x%10;x/=10;}if(len!=11)return 0;int ans=0;memset(dp,-1,sizeof dp);forr(i,1,num[len])ans+=dfs(len-1,0,i,0,i==8,i==4,i==num[len]);return ans;
}
void solve()
{int a,b;cin>>a>>b;cout<<calc(b)-calc(a-1)<<endl;
}
P2518 计数
题意：重新把所给的数各位排列组合，能得到多少更小的数
思路：可重复康托展开
康托展开速成
const int N=55,mod=1e9+7;
int c[N][N],sn[N],a[12];
int full_perm(int len){//全排列 len:剩下的位数int res=1;forr(i,0,9){res*=c[len][a[i]];len-=a[i];}return res;
}
void solve()
{string s;cin>>s;int len=s.size();forr(i,0,len-1){sn[i+1]=s[i]-'0';a[sn[i+1]]++;}//杨辉三角求组合数c[0][0]=1;forr(i,1,len){c[i][0]=c[i][i]=1;forr(j,1,i-1)c[i][j]=c[i-1][j-1]+c[i-1][j];}//开始展开int ans=0;forr(i,1,len){forr(j,0,sn[i]-1){//枚举比该位上小的数字if(a[j]){a[j]--;//让这一位上是jans+=full_perm(len-i);//求全排列a[j]++;//还回来 继续定下一个数}}a[sn[i]]--;//题意让这一位≤n[i] 那就这一位上定死是n[i] 不然之后在全排列的时候 会重复}cout<<ans<<endl;
}