Loading...

数位$dp$小结

check评论:0 条 remove_red_eye浏览量:438 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-01

数位$dp$是一类用于处理某个区间内的数字的每位之间的关系的数种类的个数的问题的方法,常见的实现方法有$dfs$和递推,本人比较喜欢$dfs$

  • $SCOI2009$ $Windy$数

    • 题目描述

    $Windy$定义了一种$Windy$数。不含前导零且相邻两个数字之差至少为$2$的正整数被称为$Windy$数。 $Windy$想知道,在$A$和$B$之间,包括$A$和$B$,总共有多少个$Windy$数?

    • 输入格式

    包含两个整数,$A$,$B$

    • 输出格式

    一个整数,代表答案

    • 输入样例$1$

      1 10
    • 输出样例$1$

      9
    • 输入样例$2$

      25 50
    • 输出样例$2$

      20
    • 数据范围

    对于$100 \%$的数据,$1\leq A,B \leq 2\times10^9$

    • 分析

    这是一种典型的数位$dp$,我们每次只需要记录上一位,然后再判断这一位即可,注意是否达到上限以及前导零

    • 代码

      #include <bits/stdc++.h>
      using namespace std;
      int dp[100][10];
      int sum[11];
      int dfs(int pos,int pre,int limit,int head)
      {
          if(pos==0)
          {
              return 1;
          }
          if(!limit&&!head&&dp[pos][pre]!=-1)
          {
              return dp[pos][pre];
          }
          int up=(limit?sum[pos]:9);
          int ans=0;
          for(int i=0;i<=up;i++)
          {
              if(!head&&abs(i-pre)<2)
              {
                  continue;
              }
              ans+=dfs(pos-1,i,limit&&i==up,head&&i==0);
          }
          if(!limit&&!head)
          {
              dp[pos][pre]=ans;
          }
          return ans;
      }
      int solve(int x)
      {
          memset(sum,0,sizeof(sum));
          memset(dp,-1,sizeof(dp));
          int cnt=0;
          while(x)
          {
              sum[++cnt]=x%10;
              x/=10;
          }
          return dfs(cnt,-1,1,1);
      }
      int main()
      {
          int l,r;
          cin>>l>>r;
          cout<<solve(r)-solve(l-1);
      }
  • 洛谷$P2110$ 欢总喊楼记

懒得打题目了qaq

我们设$dp[i][j]$代表当前搜到了第$i$为,最高位为$j$的方案数

$dfs$的时候我们记录当前位数,上一位,最高位,是否有前导零,是否达到上限即可

#include <bits/stdc++.h>
using namespace std;
long long tas[20],dp[20][12],len;
long long dfs(int pos,int pre,int maxn,int lead,int limit)
{
    if(!pos)
    {
        return maxn==pre;
    }
    if(!limit&&dp[pos][maxn]!=-1)
    {
        return dp[pos][maxn];
    }
    int up=(limit)?tas[pos]:9;
    long long ans=0;
    for(int i=0;i<=up;i++)
    {
        if(lead&&i)
        {
            ans+=dfs(pos-1,i,i,0,limit&&i==up);
        }
        else
        {
            ans+=dfs(pos-1,i,maxn,lead&&(i==0),limit&&i==up);
        }
    }
    if(!lead&&!limit)
    {
        dp[pos][maxn]=ans;
    }
    return ans;
}
long long solve(long long x)
{
    memset(tas,0,sizeof(tas));
    memset(dp,-1,sizeof(dp));
    len=0;
    while(x)
    {
        len++;
        tas[len]=x%10;
        x/=10;
    }
    return dfs(len,0,-1,1,1);
}
int main()
{
    long long l,r;
    cin>>l>>r;
    cout<<solve(r)-solve(l-1);
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名