Codeforces 914 C. Travelling Salesman and Special Numbers (数位DP)

题目链接：Travelling Salesman and Special Numbers

题意：

　　给出一个二进制数n，每次操作可以将这个数变为其二进制数位上所有1的和(3->2 ; 7->3)，现在给出了一个数k，问不大于n的数中有几个数经过k次操作可以变成1。

题解：

　　因为所给的n很大，但是可以发现只要经过一次操作，n都会变成1000以内的数，所以可以把1000以内的数的答案都存下来。每次在这里面找等于k-1的数，然后数位DP求个数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAX_N = 1e3+9;
 4 const int MOD = 1e9+7;
 5 char s[MAX_N];
 6 int len;
 7 int f[MAX_N][MAX_N];
 8 long long res[MAX_N];
 9 void init()
10 {
11     memset(f,-1,sizeof(f));
12     for(int i=1;i<=1000;i++)
13     {
14         int t = i;
15         int num = 0;
16         while(t>1)
17         {
18             int temp = 0;
19             while(t)
20             {
21                 t -= t&-t;
22                 temp++;
23             }
24             t = temp;
25             num++;
26         }
27         res[i] = num;
28     }
29 }
30 int dp(char *s,int pos,int num,int tar,int limit)
31 {
32     if(num > tar || tar>1000) return 0;
33     if(pos == len)
34     {
35         if(num == tar) return 1;
36         else return 0;
37     }
38     if(!limit && f[pos][tar-num]!=-1) return f[pos][tar-num];
39     int up = limit?s[pos]-'0':1;
40     int ans = 0;
41     for(int i=0;i<=up;i++) ans = (ans + dp(s,pos+1,i==1?num+1:num,tar,limit&&i==up))%MOD;
42     if(!limit) f[pos][tar-num] = ans;
43     return ans;
44 }
45 int main()
46 {
47     init();
48     scanf("%s",s);
49     len = strlen(s);
50     int num = 0;
51     int k;
52     cin>>k;
53     if(k==0)
54     {
55         cout<<1<<endl;
56         return 0;
57     }
58     if(k==1)
59     {
60         cout<<len-1<<endl;
61         return 0;
62     }
63     long long ans =0;
64     for(int i=0;i<len;i++) if(s[i] == '1') num++;
65     for(int i=1;i<=1000;i++)
66     {
67         if(res[i] == k-1)
68         {
69             ans = (ans + dp(s,0,0,i,1))%MOD;
70             //cout<<"...."<<i<<"....."<<dp(s,0,0,i,1)<<endl;
71         }
72     }
73     cout<<ans<<endl;
74 }