[动态规划](5)数位统计DP

数位统计DP

模板题:338. 计数问题 - AcWing题库

image-20210707154718146

思路:枚举每一位上 [ 0 ~ 9 ] 出现的次数,例如:

  • n = abcdefg (一个七位数) 求 在 1~n 中 1在第四位上出现的次数
    • 当 1 <= xxx1yyy <= abcdefg
      1. xxx = 000 ~ abc - 1 ,yyy = 000~999 次数 = abc * 1000
      2. xxx = abc
      3. d < 1 , abc1yyy > abc0efg,次数为0
      4. d = 1 , yyy=000~efg,次数为efg+1
      5. d > 1 , yyy = 000 ~ 999 , 次数为1000

代码:

```C++

include

include

include

using namespace std; int get_num(int x) {//返回x的位数 int res = 0; while (x) { res++; x /= 10; } return res; } int dp(int x,int n) {//返回x在1-n中出现的次数 int res = 0; int d = get_num(n); for (int i = 1; i <= d; i++) {//从第一位开始枚举 //l和r是第i位左边和右边的整数(例如n=abcdefg,i=4,则l为abc,r为efg) int p = pow(10,i-1);//计算第i位处于10的多少次方,用于计算abc和efg int l = n / p / 10, r = n % p, di = n / p % 10;

    //计算第i位左边的整数小于1(视频中xxx=000 到 abc-1)的情况
    if (x) res += l * p;
    if (!x && l)res += (l - 1) * p;//如果 x = 0,左边高位不能全为0(视频中xxx = 001 到 abc - 1)
    //计算第j位左边的整数等于1(视频中xxx = abc)的情况
    if ((di > x) && (x || l)) res += p;
    //如果当前第i位的数大于x,且x大于0或左边的abc大于0的话,方案即等于第i位位数的值
    if ((di == x) && (x || l)) res += r + 1;
    //如果当前第i位的数等于x的话,且在x与左边的整数abc不为0的情况,方案数只等于右边的数加1
}
return res;

} int main() { int a, b; while (cin >> a >> b, a || b) { if (a > b) swap(a, b);//注意输入有可能不是按递增输入 for (int i = 0; i <= 9; i++) cout << dp(i, b) - dp(i, a - 1) << " "; //枚举每一位的出现次数,利用求区间和的思想计算出a-b中i出现的次数 cout << endl; }

return 0;

}



a

本文链接:

https://nullcode.fun/154.html
1 + 3 =
快来做第一个评论的人吧~