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求个数。

 #include<bits/stdc++.h>

 using namespace std;

 const int MAX_N = 1e3+;

 const int MOD = 1e9+;

 char s[MAX_N];

 int len;

 int f[MAX_N][MAX_N];

 long long res[MAX_N];

 void init()

 {

     memset(f,-,sizeof(f));

     for(int i=;i<=;i++)

     {

         int t = i;

         int num = ;

         while(t>)

         {

             int temp = ;

             while(t)

             {

                 t -= t&-t;

                 temp++;

             }

             t = temp;

             num++;

         }

         res[i] = num;

     }

 }

 int dp(char *s,int pos,int num,int tar,int limit)

 {

     if(num > tar || tar>) return ;

     if(pos == len)

     {

         if(num == tar) return ;

         else return ;

     }

     if(!limit && f[pos][tar-num]!=-) return f[pos][tar-num];

     int up = limit?s[pos]-'':;

     int ans = ;

     for(int i=;i<=up;i++) ans = (ans + dp(s,pos+,i==?num+:num,tar,limit&&i==up))%MOD;

     if(!limit) f[pos][tar-num] = ans;

     return ans;

 }

 int main()

 {

     init();

     scanf("%s",s);

     len = strlen(s);

     int num = ;

     int k;

     cin>>k;

     if(k==)

     {

         cout<<<<endl;

         return ;

     }

     if(k==)

     {

         cout<<len-<<endl;

         return ;

     }

     long long ans =;

     for(int i=;i<len;i++) if(s[i] == '') num++;

     for(int i=;i<=;i++)

     {

         if(res[i] == k-)

         {

             ans = (ans + dp(s,,,i,))%MOD;

             //cout<<"...."<<i<<"....."<<dp(s,0,0,i,1)<<endl;

         }

     }

     cout<<ans<<endl;

 }

巴特西

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

最新文章

热门文章