Count SIN Numbers

Count SIN Numbers

题目链接：http://codeforces.com/group/gRkn7bDfsN/contest/211954/problem/D

数位DP

定义状态：dp[当前第i位数][当前位上的数字j][前i位数是否与给定数s相同][当前位上的数是否为谷值][前i位数所代表的数是否前导零]表示从零到长为i末尾数字为j的符合状态的数的个数。

状态转移方程：

当前位上的数为谷值且前导零时，下一位只能为零：

　　dp[i+1][0][k&(0==s[i]-'0')][!m][n==1]+=dp[i][j][k][m][n];

否则可取下一位数为p，for p in range(l,r+1):

　　dp[i+1][p][k&(p==s[i]-'0')][!m][n==1&&p==0]+=dp[i][j][k][m][n]，其中l和r的值由前i位数是否与给定数s相同以及当前位上的数是否为谷值共同决定。

故A到B满足条件的数的个数=从零到B符合条件的数的个数-从零到A符合条件的数的个数+（A符合条件？1:0）

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <string>
 5 using namespace std;
 6 typedef long long ll;
 7 ll dp[20][10][2][2][2],ans;
 8 string a,b;
 9 ll js(string s){
10     ll len=s.length();
11     memset(dp,0,sizeof(dp));
12     dp[0][0][1][1][1]=dp[0][0][1][0][1]=1LL;
13     for(int i=0;i<len;++i)
14     for(int j=0;j<=9;++j)
15     for(int k=0;k<2;++k)
16     for(int m=0;m<2;++m)
17     for(int n=0;n<2;++n){
18         if(dp[i][j][k][m][n]){
19             int l=0,r=(k==1?s[i]-'0':9);
20             if(n!=1){
21                 if(m==0)r=min(r,j-1);
22                 else l=j+1;
23             }
24             if(0<=l&&r<=9&&l<=r){
25                 if(m==1&&n==1){
26                     dp[i+1][0][k&(0==s[i]-'0')][!m][n==1]
27                             +=dp[i][j][k][m][n];
28                 }else{
29                     for(int p=l;p<=r;++p)
30                         dp[i+1][p][k&(p==s[i]-'0')][!m][n==1&&p==0]
31                             +=dp[i][j][k][m][n];
32                 }
33             }
34         }
35     }
36     ll t=0;
37     for(int j=0;j<=9;++j)
38     for(int k=0;k<2;++k)
39     for(int m=0;m<2;++m)
40     for(int n=0;n<2;++n)
41         t+=dp[len][j][k][m][n];
42     return t-2;
43 }
44 int main(void){
45     cin>>a>>b;
46     ans=js(b)-js(a)+1;
47     for(int i=1;i<(int)a.length();++i)
48     if((i%2==1&&a[i]<=a[i-1])||(i%2==0&&a[i]>=a[i-1])){
49         ans--;
50         break;
51     }
52     cout<<ans<<endl;
53 }
54