DP(解碼)

題意：給出一個串的長度n，串只有0,1組成，但是不能有兩個相鄰的1。按字典序給串排列，最先肯定是0000，接著是0001，依此類推。給一個數字m，輸出在長度為n的情況下，第m個排列的串是什么，如果m大于總排列數，輸出-1

?

這其實是一個解碼的過程，必須用高位到低位解碼（從左到右），因為這里要求字典序，字典序的比較水從左到右的

由于數據規(guī)模固定在串長度44以內，所以我們先dp出所有長度下可能的排列數，編碼時也要用

每次編碼按位編碼，判斷當前位為0還是為1，就是看填0或1可能產生多少排列數然后和m比較，這個看代碼大概都能懂的

?

#include <cstdio> #include <cstring> #define N 55 long long dp[N][2];int main() {memset(dp,0,sizeof(dp));dp[1][1]=dp[1][0]=1;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];}int n; long long m; int ans[N];while(scanf("%d%lld",&n,&m)!=EOF){if(m>dp[n][0]+dp[n][1]) { printf("-1\n"); continue; }while(n){if(dp[n][0] >= m) //當前位填0已經滿足printf("0");else //填0不滿足 {m-=dp[n][0];printf("1");}n--;}printf("\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的Ural(Timus) 1081. Binary Lexicographic Sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。