AT1483题解

Z_M__ · 2021-04-22 21:23:27 · 题解

这题是一道数位DP。

1. 状态表示: 我们设f[i][j][k]表示所有数位为i位\;且\;最高位为j\;出现数字k的次数,（如f[2][1][1]=11,因为10~19间出现了11次1）。（其实这题不用3维，但为了更好享用多倍经验，所以...）

2.状态转移： 先给些柿子

（1）

（2）

（3）

• 首先对于1位数我们可以直接赋值，f[1][0][0] = f[1][1][1] =f[1][2][2]...f[1][9][9] = 1

• 其他不是1位数的，则是上面的柿子2。 比如f[3][1][1]表示的(是所有3位数且最高位为1的数中出现数字1的次数)就是100到199中出现数字1的次数，如果去掉最高位的1，那剩下的数就是0到99，也就是所有两位数和一位数，由于我们是从1位数开始枚举转移的，所以我们现在已经有了f[2][0...9][1]这只是f[3][1][1]的一部分（后面两位数的部分），还有一部分就是最高位1，所以100-199这些数每个数都对f[3][1][1]有1的贡献，所以f[3][1][1]+=pow(10,2),这就是柿子3。

for (int i = 0; i <= 9; i++)//柿子1
    f[1][i][i] = 1; //显然！
for (int i = 2; i <= 9; i++)//枚举当前位数
{
    for (int j = 0; j <= 9; j++)//枚举最高位
    {
      for (int k = 0; k <= 9; k++)
            for (int l = 0; l <= 9; l++)//枚举上1位数的最高位
            f[i][j][k] += f[i - 1][l][k];//柿子2
        f[i][j][j] += pow (10, i -1);//柿子3
    }
}

3.计算答案： 由于f[i][j][k]中的只是一段一段的，所以在计算答案时也要分段求:

• 举个栗子: n=433 是，算出现1的次数：

• 第一段： 1-99

  我们有1-9,f[2][1][1](10-19),f[2][2][1](20-29)...f[2][9][1](90-99)

• 第二段： 100-399

  我们有f[3][1][1](100-199),f[3][2][1](200-299)

• 第三段: 400-433

  这时我们最高位只能是4了，所以只要枚举后两位就行了，但如果最高位是1的话那么第三段的所有数对答案都多有1的贡献，这时要加上pow(10,3-1)，分开枚举则为f[2][0][1](400-409),f[2][1][1](410-429)，最后只剩430-433了，也就是f[1][1][0]f[1][1][1](431),f[1][2][1](432),f[1][3][1](434)

  #include <bits/stdc++.h> 
  #define int long long//要开longlong，数据有问题
  using namespace std;
  const int MAXN = 1e2;
  int n, f[MAXN][22][22];
  void init ()
  {
  for (int i = 0; i <= 9; i++)//柿子1
      f[1][i][i] = 1; //显然！
  for (int i = 2; i <= 9; i++)//枚举当前位数
  {
      for (int j = 0; j <= 9; j++)//枚举最高位
      {
        for (int k = 0; k <= 9; k++)
              for (int l = 0; l <= 9; l++)//枚举上1位数的最高位
              f[i][j][k] += f[i - 1][l][k];//柿子2
          f[i][j][j] += pow (10, i -1);//柿子3
      }
  }
  }
  int sum (int x, int num)
  {
  int a[10] = {}, len = 0, sum = 0;
  while (x)
  {
      a[++len] = x % 10;
      x /= 10;
  }
  
  for (int i = 1; i <= len - 1; i++)//第一段 (1-9,不能是0，因为不能有前导0)
      for (int j = 1; j <= 9; j++)
          sum += f[i][j][num];
  
  for (int i = 1; i <= a[len] - 1; i++)//第二段 
      sum += f[len][i][num];
  
  for (int i = len - 1; i >= 1; i--)//第三段 
  {
      for (int j = 0; j <= a[i] - 1; j++)//可以是0，以为前面已经确定了非0数 
          sum += f[i][j][num];
  
      for (int j = len; j > i; j--)//不要忘了这!! 
          if (a[j] == 1)
             sum += a[i] * pow (10, i - 1);
  }
  return sum;
  }
  signed main ()
  {
  init ();
  cin >> n;
  cout << sum (n + 1, 1) << endl;//n+1是因为sum()中只统计到x-1 
  return 0;
  }