LightOJ1105 Fi Binary Number（数位DP）

题目要求第k个没有连续两个1的二进制数。

这算数位DP吧，只不过以前遇到的是统计区间的数字情况，而这题是求第几个数字，差不多是反过来的。

本来我想用状态dp[i][0/1]表示长度i末尾0或1的二进制数个数，发现这样好像没法解。

最后需要根据数位DP状态的值推算出要求二进制数各个位置是0还是1，这个肯定是从高位到低位确定——所以应该反过来表示状态：

dp[i][0/1]：长度i开头为0或1的二进制数个数

最后的求解：

先利用dp[i][1]的值确定出要求二进制的位数
位数知道后，最高位得是1
最后就从高到低根据前一位是0还是1、dp[i][0]的值和剩下的个数的关系一位位确定。

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define MAXL 100

 int d[MAXL][];

 int main(){

     d[][]=;

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

         d[i][]=d[i-][]+d[i-][];

         d[i][]=d[i-][];

     }

     int t,n;

     scanf("%d",&t);

     for(int cse=; cse<=t; ++cse){

         scanf("%d",&n);

         int len=;

         while(n>d[len][]){

             n-=d[len][];

             ++len;

         }

         printf("Case %d: 1",cse);

         int last=;

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

             if(last==){

                 putchar('');

                 last=;

             }else if(n>d[len-i][]){

                 n-=d[len-i][];

                 putchar('');

                 last=;

             }else{

                 putchar('');

                 last=;

             }

         }

         putchar('\n');

     }

     return ;

 }

巴特西

LightOJ1105 Fi Binary Number（数位DP）

最新文章

热门文章