精华内容
下载资源
问答
  • 数位DP

    2018-12-10 08:00:00
    数位DP

    数位DP
    题目:HDU 2089
    给出l,r,问[l,r]中各数位没有4,62的数个数
    in 1 63
    out 47

    解释:
    数位上不能有4也不能有连续的62,没有4的话在枚举的时候判断一下,不枚举4就可以保证状态合法了,所以这个约束没有记忆化的必要,而对于62的话,涉及到两位,当前一位是6或者不是6这两种不同情况我计数是不相同的,所以要用状态来记录不同的方案数
    dp[pos][sta]表示当前第pos位,前一位是否是6的状态,这里sta只需要去0和1两种状态就可以了,不是6的情况可视为同种,不会影响计数

    #include<bits/stdc++.h>
    using namespace std;
    int a[10],dp[10][2];                //DPIJ是指第I位至最低位为止,上一位是6与不是6的方案数
    int dfs(int pos,int pre,int flag){  //传入当前位的下标,上一位的数,当前位是否有限制
        if(pos==-1)return 1;            //因为POS是从0开始存的,-1就表示扫完了
        if(!flag && dp[pos][pre==6]!=-1)return dp[pos][pre==6];//当前位无限制时且对应的DP状态已经更新,直接返回
        int tmp=0,up=(flag?a[pos]:9);   //当前位方案数初始化,最高位初始化
        for(int i=0;i<=up;i++){         //当前POS位的值从0到UP扫一次
            if((pre==6&&i==2)||(i==4))continue; //当前位是4或者上一位是6且当前位是2就跳出
            tmp+=dfs(pos-1,i,flag&&i==a[pos]);  //传入下一位的下标,当前位的数,下一位是否有限制
        }
        if(!flag) dp[pos][pre==6]=tmp;  //更新DP方便下次直接使用,
        return tmp;                     //返回当前位的方案数
    }
    int solve(int x){       //求一到X有多少个数
        int pos=0;          //位置初始化
        memset(dp,-1,sizeof(dp));//init dp 可以不同,DP只是为了加速
        while(x>0){         //把X逐位转成数组存
            a[pos++]=x%10;  //读出个位且下标加1
            x/=10;          //右移一位
        }
        return dfs(pos-1,0,1);//深搜,传入下一位的下标,当前位的数,是否有限制
    }//有限制的意思是到当前位为止,此搜索路径的高位全部与X相同,例如X是5555,当前扫到55Y,则Y位就是有限制的
    int main(){
        int le,ri;                      //定义左右界
        while(cin>>le>>ri&&le+ri!=0)    //输入左右界
            cout<<(solve(ri)-solve(le-1))<<endl;//然后就求了
        return 0;
    }
    /*
    1 100
    80
    
    1 63
    47
    */
    
    
    
    展开全文
  • 数位dp

    2020-08-17 11:44:25
    数位dp 数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位…数的...

    数位dp

    数位dp是一种计数用的dp,一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp,字面意思就是在数位上进行dp咯。数位还算是比较好听的名字,数位的含义:一个数有个位、十位、百位、千位…数的每一位就是数位啦!

    之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式,使得新的枚举方式满足dp的性质,然后记忆化就可以了。

    windy数

    不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。求a,b之间有几个windy数

    输入格式
    输入只有一行两个整数,分别表示 a和 b

    输出格式
    输出一行一个整数表示答案。

    输入输出样例
    输入
    1 10
    输出
    9
    输入
    25 50
    输出
    20

    #include<iostream>
    using namespace std;
    
    const int MAX = 10;
    int dp[MAX][10];
    int max[MAX];
    int a, b;
    
    int dfs(int pos, int pre,bool lead, bool flag)
    {
    	cout << pos << ' ' << pre << ' ' << lead << ' ' << flag << endl;
    	if (pos == 0)
    	{
    		return 1;
    	}
    	if (!flag&&!lead&&dp[pos][pre] != -1)
    		return dp[pos][pre];
    	int max_num = (flag ? max[pos] : 9);
    	cout << max_num << endl;
    	int cnt = 0;
    	for (int i = 0; i <= max_num; i++)
    	{
    		if (!lead&&abs(i - pre) < 2)
    			continue;
    		cnt += dfs(pos - 1, i, lead && (i == 0), flag && (i == max_num));
    	}
    	if (!lead&&!flag)dp[pos][pre] = cnt;
    	return cnt;
    }
    
    
    int solve(int n)
    {
    	int pos = 0;
    	while (n)
    	{
    		max[++pos] = n % 10;
    		n /= 10;
    	}
    	memset(dp, -1, sizeof(dp));
    	return dfs(pos, -1, true, true);
    }
    
    int main()
    {
    	cin >> a;
    
    	cout << solve(a)<< endl;
    	system("pause");
    	return 0;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,206
精华内容 6,482
关键字:

数位dp