发布于 由itewqq

[DP][数位DP] HDU 2089 不要62

数位DP入门题，其实只要搞懂dp[i][j]存的是什么就行了。

用搜索解法的话，每次相当于枚举了比当前位小的所有数字，然后需要记录下是不是上界（第一位）。就题目而言的话还需要记录前面一位是不是6（这决定了当前位可不可以是2）,记忆化的话有一点是当如果是上界（第一位）的时候是不能记忆的，因为记忆话那个其实是存了第len位长的前缀为/不为6的当前位可以从0到9的所有数中的答案，注意这里这个东西是和给定的什么串无关的，同时他也不能有关，因为这个不能把信息完全表示出来。所以只有在不是上届的时候才保存记忆化结果。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
typedef long long LL;
const int maxn=17+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

int vis[10][2],a[10];

int dfs(int len,int is6,int isf)//if isf == 1 cannot use vis to describe it
{
    if(!len)return 1;
    if(!isf&&vis[len][is6]!=-1)return vis[len][is6];
    int n= isf?a[len]:9;
    int res=0;
    for (int i=0;i<=n;i++)
    {
        if(i==4||i==2&&is6)
            continue;
        res+=dfs(len-1,i==6,isf&&i==n);
    }
    if(!isf)
        vis[len][is6]=res;
    return res;
}

int  f(int n)
{
    int top=0;
    while(n)
    {
        a[++top]=n%10;
        n/=10;
    }
    return dfs(top,0,1);
}



int main()
{
    int n,m;
    memset(vis,-1,sizeof(vis));//只需要一次初始化，因为这个保存的东西是和给的什么串无关的
    while(~scanf("%d%d",&n,&m)&&m)
    {
        cout<

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。