数据结构算法（求数组中非0位的数字个数）

题意：
给你一个数N，然后让你求[1,n]中恰好有kk位非0位的数字的个数。
思路：数位DP
套路性地，设 f[i][j] 表示长度为 i 的数字串，有 j 个非零数位的方案数，转移方程
f[i][j]=f[i−1][j]+9f[i−1][j−1]
然后预处理出f[i][j]
具体操作看代码吧

#include<iostream> #include<cstdio> #include <stdio.h> #include<algorithm> #include<cstring> #include <string> #include<cmath> #include<cstdlib> #include<queue> #include<map> #include<vector> #include<bits/stdc++.h> #include <set> #define ll   long long #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define inf 0x3f3f3f3f3f3f3f3f #define pi 3.1415926535898 #define N 500050 using namespace std; char a[10010]; int n,k,ans,f[1050][5];//表示第i位有J个非零数位的方案数 int main() { cin>>a+1; cin>>n; int len=strlen(a+1); for(int i=1; i<=len; i++) a[i]-='0'; f[0][0]=1; for(int i=1; i<=len; i++) { f[i][0]=f[i-1][0]; for(int j=1; j<=3; j++) { f[i][j]=f[i-1][j]+9*f[i-1][j-1];//预处理 } } int cnt=0; for(int i=1; i<=len; i++) { if(a[i]) { if(n-cnt>=0) ans+=f[len-i][n-cnt];//接下来还有（len-i）位数，n-cnt的非零位 } if(a[i]>1) { if(n-cnt-1>=0) ans+=(a[i]-1)*f[len-i][n-cnt-1];//本位可以取非零位 } if(a[i]) ++cnt; } if(cnt==n) ++ans; cout<<ans; return 0; } 

本文地址：https://blog.csdn.net/CHAI_NIAOJINJE/article/details/107757432