数_位_dp

  • 时间:
  • 来源:互联网
  • 文章标签:

eg.[不要62](http://acm.hdu.edu.cn/showproblem.php?pid=2089)

 


```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
int a[20];
int dp[20][2];
int dfs(int pos,int pre,int sta,bool limit)
{
//位数,前面的数,前面是否是6,是否有限制
    if(pos==-1) return 1;//    

    if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];
    //dp[pos][sta]表示当前第pos位,前一位是否是6的状态
    //若未使用过,直接调用以前用过的
    int up=limit ? a[pos] : 9;
    int tmp=0;
    for(int i=0;i<=up;i++)
    {//枚举每一位
        if(pre==6 && i==2)continue;
        if(i==4) continue;//都是保证枚举合法性
        tmp+=dfs(pos-1,i,i==6,limit && i==a[pos]);//要想有限制,必须前面有限制,并且数字是a[pos](<a[pos])..
    }
    if(!limit) 
          dp[pos][sta]=tmp;//记忆化(必须没有限制)
    return tmp
    ;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;//统一往下挪了一位
        x/=10;
    }
    return dfs(pos-1,-1,0,true);//减回去,pos-1
}
int main()
{
    int le,ri;
    //memset(dp,-1,sizeof dp);可优化
    while(~scanf("%d%d",&le,&ri) && le+ri)
    {
        memset(dp,-1,sizeof dp);
        printf("%d\n",solve(ri)-solve(le-1));
    }
    return 0;
}

```
 

本文链接http://www.taodudu.cc/news/show-1782072.html