Loading...

洛谷P2110 欢总喊楼记

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

数位$dp$

我们设$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);
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名