首页 > 代码库 > 数位dp模板

数位dp模板

 1 //HDU - 5787为例
 2 //求区间[L,R]内,任意相邻k位(如果位数不足k,就是全部的数位)没有两两相同的数位的数的个数
 3 LL l,r;
 4 int k;
 5 int num[20];
 6 LL dp[20][10010][5];
 7  //pos表示当前处理的位置(一般从高到低)
 8  //limit是限制当前这位能否随便取,即决定top=num[pos]或top=9。
 9  //非limit的状态可以记录起来,因为此时pos后面的数字都可以随便取,所以状态是一样的。
10  //pre表示上一位的数字或是上一个状态的数字
11  //dig是表示目前最多几位数字相邻数字互不相同。
12 LL dfs(int pos,int limit,int pre,int dig)
13 {
14    
15     LL res=0;
16     if(pos<0)return 1;
17     if(!limit&&dp[pos][pre][dig]!=-1)return dp[pos][pre][dig];
18     int top=limit?num[pos]:9;
//---------------------只需根据题意修改for循环的语句即可------------------------------
19 for(int i=0;i<=top;i++) 20 { 21 int j; 22 int s=pre; 23 for(j=0;j<dig;j++) 24 { 25 if(s%10==i)break; 26 else s/=10; 27 } 28 if(j!=dig)continue; 29 if(i==0&&dig==0)res+=dfs(pos-1,limit&&(i==num[pos]),pre,dig); 30 res+=dfs(pos-1,limit&&(i==num[pos]),(pre%1000)*10+i,min(dig+1,k-1)); 31 }
//--------------------------------------------------------------------------------
32 if(!limit)dp[pos][pre][dig]=res; 33 return res; 34 } 35 LL solve(LL n) 36 { 37 int cnt=0; 38 mt(dp,-1); 39 while(n) 40 { 41 num[cnt++]=n%10; 42 n/=10; 43 } 44 return dfs(cnt-1,1,0,0); 45 } 46 int main() 47 { 48 #ifdef Local 49 freopen("data.txt","r",stdin); 50 #endif 51 ios::sync_with_stdio(false); 52 cin.tie(0); 53 while(cin>>l>>r>>k) 54 { 55 cout<<solve(r)-solve(l-1)<<endl; 56 } 57 return 0; 58 #ifdef Local 59 cerr << "time: " << (LL) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl; 60 #endif 61 }

 

数位dp模板