多校5 HDU5787 K-wolf Number 数位DP-白红宇

多校5 HDU5787 K-wolf Number 数位DP

阅读量：5138 次

发布时间：2019-06-13

本文共 2728 字，大约阅读时间需要 9 分钟。

1 // 多校5 HDU5787 K-wolf Number 数位DP  2 // dp[pos][a][b][c][d][f] 当前在pos，前四个数分别是a b c d  3 // f 用作标记，当现在枚举的数小于之前的数时，就不用判断i与dig[pos]的大小  4 // 整体来说就，按位往后移动，每次添加后形成的数都小于之前的数，并且相邻k位不一样，一直深搜到cnt位  5 // http://blog.csdn.net/weizhuwyzc000/article/details/52097690  6   7   8   9 // #pragma comment(linker, "/STACK:102c000000,102c000000") 10 #include 
     
       11 #include 
      
        12 #include 
       
         13 #include 
        
          14 #include 
         
           15 #include 
          
            16 #include 
           
             17 #include 
             18 #include 
             
               19 #include 
              
                20 #include 
               
                 21 #include 
                
                  22 #include 
                 
                   23 // #include 
                  
                    24 using namespace std; 25 #define clc(a,b) memset(a,b,sizeof(a)) 26 const double inf = 0x3f3f3f3f; 27 #define lson l,mid,rt<<1 28 // #define rson mid+1,r,rt<<1|1 29 const int N = 2010; 30 const int M = 1e6+10; 31 const int MOD = 1e9+7; 32 #define LL long long 33 #define LB long double 34 // #define mi() (l+r)>>1 35 double const pi = acos(-1); 36 const double eps = 1e-8; 37 void fre(){freopen("in.txt","r",stdin);} 38 void freout(){freopen("out.txt","w",stdout);} 39 inline int read(){ int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') { if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;} 40 41 LL l,r,cnt; 42 int k; 43 int dig[19]; 44 LL dp[19][11][11][11][11][2]; 45 int vis[19][11][11][11][11][2]; 46 int cas; 47 LL dfs(LL pos,int a,int b,int c,int d,int f){ 48 if(pos==cnt) return 1LL; 49 if(vis[pos][a][b][c][d][f]==cas) return dp[pos][a][b][c][d][f]; 50 vis[pos][a][b][c][d][f]=cas; 51 LL ans=0; 52 if(f){ 53 for(int i=0;i<10;i++){ 54 if(k==2) { if(d==i) continue;} 55 else if(k==3) { if(d==i||c==i) continue;} 56 else if(k==4) { if(d==i||c==i||b==i) continue;} 57 else { if(d==i||c==i||b==i||a==i) continue;} 58 if(i==0){ 59 if(d==10) ans+=dfs(pos+1,a,b,c,d,f); 60 else ans+=dfs(pos+1,b,c,d,i,f); 61 } 62 else ans+=dfs(pos+1,b,c,d,i,f); 63 } 64 } 65 else{ 66 for(int i=0;i<10;i++){ 67 if(k==2) { if(d==i) continue;} 68 else if(k==3) { if(d==i||c==i) continue;} 69 else if(k==4) { if(d==i||c==i||b==i) continue;} 70 else { if(d==i||c==i||b==i||a==i) continue;} 71 if(i
                   
                    =max(0,i-k+1);j--){ 94 if(dig[i]==dig[j]) return false; 95 } 96 } 97 return true; 98 } 99 int tem[19];100 int main(){101 while(~scanf("%I64d%I64d%d",&l,&r,&k)){102 cnt=0;103 while(r) tem[cnt++]=r%10,r=r/10;104 int k=0;105 for(int i=cnt-1;i>=0;i--) dig[k++]=tem[i];106 cas++;107 LL ans1=dfs(0,10,10,10,10,0);108 cnt=0,k=0;109 while(l) tem[cnt++]=l%10,l=l/10;110 111 for(int i=cnt-1;i>=0;i--) dig[k++]=tem[i];112 cas++;113 LL ans2=dfs(0,10,10,10,10,0);114 if(ck()) ans2--; 115 printf("%I64d\n",ans1-ans2);116 }117 return 0;118 }