hihoCoder 1033

题目链接：

http://hihocoder.com/problemset/problem/1033

听说这个题是xiaodao出的~~

我们要知道dp其实就是一个记忆化搜索的过程，如果某个子结构之前搜索过了，那么这次我们就不搜索了。

所以数位dp记录的其实就是dp[pos][state]pos位以内满足条件state的情况数。

当然，作为第二次做数位dp的渣渣，我觉得还是得强调几点：

1、一定要记录一个limit，代表这一位的取数是否受限制。

2、记录一个flag，代表之前的数是否都是前导0。

3、注意(!flag&&!limit)的情况下再给dp[pos][state]赋值。

剩下的好像就没啥了。。。dfs就行，注意递归结束条件。。。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 
  5 using namespace std;
  6 const int maxn = 20;
  7 const int maxs = 300;
  8 const long long mod = 1000000000 + 7;
  9 
 10 typedef long long int64;
 11 
 12 typedef struct Node{
 13   int64 cnt, sum;
 14 
 15   Node(){
 16     cnt = sum = 0;
 17   }
 18 
 19   Node( int64 cnt, int64 sum ){
 20      this->cnt = cnt;
 21      this->sum = sum;
 22   }
 23 
 24   Node(const struct Node& node){
 25     cnt = node.cnt;
 26     sum = node.sum;
 27   }
 28 }Node;
 29 
 30 Node dp[maxn][maxs][2];
 31 int64 l, r;
 32 int k;
 33 
 34 int64 c[maxn];
 35 int digit[maxn];
 36 
 37 void Init(void){
 38   c[0] = 1;
 39   for( int i = 1; i <= 18; ++i ){
 40     c[i] = (c[i-1] * 10)%mod;
 41   }
 42 }
 43 
 44 Node dfs( int pos, int sum, int p, int flag, int limit ){
 45   Node ans;
 46   if( sum < 0 || sum > 200 )
 47      return Node(0, 0);
 48 
 49   if( pos < 0 ){
 50     if(flag)
 51       ans.cnt = 0;
 52     else
 53       ans.cnt = (sum == 100) ? 1 : 0;
 54     ans.sum = 0;
 55     return ans;
 56   }
 57 
 58   if(!flag && !limit && dp[pos][sum][p].cnt != -1)
 59     return dp[pos][sum][p];
 60   int last = limit ? digit[pos] : 9;
 61 
 62   Node a;
 63   ans.cnt = 0, ans.sum = 0;
 64   for( int i = 0; i <= last; ++i ){
 65     if( i == 0 && flag ){
 66       a = dfs( pos-1, sum, p, flag, limit&&(i == last) );
 67     }else{
 68       if(p){
 69         a = dfs( pos-1, sum-i, p^1, 0, limit&&(i == last) );
 70       }else{
 71         a = dfs( pos-1, sum+i, p^1, 0, limit&&(i == last) );
 72       }
 73     }
 74     ans.cnt = (ans.cnt + a.cnt + mod)%mod;
 75     ans.sum = (ans.sum + (c[pos]*i%mod*a.cnt)%mod + a.sum + mod)%mod;
 76   }
 77 
 78   if(!limit && !flag){
 79     dp[pos][sum][p].cnt = ans.cnt;
 80     dp[pos][sum][p].sum = ans.sum;
 81   }
 82 
 83   return ans;
 84 }
 85 
 86 int bitSet( int64 num ){
 87   int len = 0;
 88   memset( digit, 0, sizeof(digit) );
 89 
 90   while(num){
 91     digit[len++] = num%10;
 92     num /= 10;
 93   }
 94 
 95   return len-1;
 96 }
 97 
 98 void InitDP(void){
 99   memset( dp, -1, sizeof(dp) );
100 }
101 
102 void solve(void){
103   InitDP();
104 
105   int len;
106   len = bitSet(l-1);
107   //cout << "len1: " << len << endl;
108   Node ans1 = dfs(len, k+100, 1, 1, 1);
109   //cout << ans1.sum << endl;
110   len = bitSet(r);
111   //cout << "len2: " << len << endl;
112   Node ans2 = dfs(len, k+100, 1, 1, 1);
113 
114   printf("%lld
", ((ans2.sum - ans1.sum + mod)%mod));
115 }
116 
117 int main(void){
118   Init();
119   while(scanf("%lld%lld%d", &l, &r, &k) != EOF){
120     solve();
121   }
122 
123   return 0;
124 }

View Code

注意下dfs过程中sum不能小于0或超过200。