ural Binary Lexicographic Sequence (dp + dfs)

本文主要是介绍ural Binary Lexicographic Sequence (dp + dfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.timus.ru/problem.aspx?space=1&num=1081

有一个二进制序列，定义为不能有两个连续的1出现，才是合法的。给出序列的长度n，求合法的二进制序列中按字典序排序后第k个序列是什么。

设dp[i][0]和dp[i][1]分别表示第i位上是0和1的个数。

那么dp[i][0] = dp[i-1][0] + dp[i-1][1]；dp[i][1] = dp[i-1][0]，打表发现和斐波那契数列相似。

求第k个合法的序列时，因为是按字典序排序，可以发现当 k >= dp[n-1]时这一位取1，否则这一位取0。

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4010;int dp[50][2],tmp[50];
void init()
{memset(dp,0,sizeof(dp));dp[1][0] = dp[1][1] = 1;tmp[1] = 2;for(int i = 2; i < 44; i++){dp[i][0] += (dp[i-1][0] + dp[i-1][1]);dp[i][1] += dp[i-1][0];tmp[i] = dp[i][0] + dp[i][1];}
}void dfs(int n, int k)
{if(n == 1){if(k == 1)printf("0");elseprintf("1");return;}if(k <= tmp[n-1]){printf("0");dfs(n-1,k);}else{printf("1");dfs(n-1,k-tmp[n-1]);}
}int main()
{init();int n,k;while(~scanf("%d %d",&n,&k)){if(k > tmp[n]){printf("-1\n");continue;}dfs(n,k);printf("\n");}return 0;
}

这篇关于ural Binary Lexicographic Sequence (dp + dfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---