本文共 1533 字，大约阅读时间需要 5 分钟。

【题目描述】

Jzabc对多米诺骨牌有很大的兴趣，然而他的骨牌比较特别，只有黑的和白的。他觉得如果存在连续三个骨牌是同种颜色的，那这个骨牌排列就是不美观的。现在他有N个骨牌要排列，他想知道不美观的排列的个数。他想请你帮忙进行统计不美观排列的个数。

【输入格式】

只有一个正整数，即要排列的骨牌的个数。

【输出格式】

一个数，即不美观的排列的个数。

【输入样例】

4

【输出样例】

6

解释：有6中不美观的排列。

【数据规模】

对于20%的数据，满足N<=60

对于50%的数据，满足N<=600

对于100%的数据，满足N<=20000

一开始不会 就没再做

后来小伙伴们提醒了一下有规律

于是打表1-10

发现G(i+1)可以由Gi*2+一个具有斐波那契数列性质的数列中某一项推出

所以递推出的Gi

由于数据太大 用到了压8位高精度

#include
   
    #include
    
     #include
     
      using namespace std;int f[4][811];int z[811];int m,n=1,a,b,c;void print(int s[811]){    int a;    for(a=800;a>1;a--)if(s[a])break;    cout<
      
       99999999)    {        s[a+1]=s[a+1]+s[a]/100000000;        s[a]%=100000000;    }}void addf(){    int a;    n++;    n%=3;    int l=(n-2+3)%3;    int r=(n-1+3)%3;    for(a=1;a<=800;a++)f[n][a]=f[l][a]+f[r][a];    jinwei(f[n]);}void cheng(){    int a;    for(a=1;a<=800;a++)z[a]*=2;    jinwei(z);}void jia(){    int a;    for(a=1;a<=800;a++)z[a]+=f[n][a];    jinwei(z);}int main(){    freopen("domino.in","r",stdin);    freopen("domino.out","w",stdout);    scanf("%d",&m);    if(m<3)    {        cout<<0<
      
     
    
   

考虑美观的情况，设f[i]为i个骨牌的排列中完美排列的数量。若在第i个位置上放与i-1个骨牌颜色相同的骨牌，则情况数为f[i-2]，否则为f[i-1]，那么f[i]:=f[i-1]+f[i-2]。由二进制的数量可得，此时不完美排列个数即为g[i]:=2^n-f[i]。

这个想法简直是dbl...瞬间就跪烂了

我的理解是

当i与i-1颜色不同时

不会影响完美排列数 所以f[i]=f[i-1]

当颜色相同时

就有可能影响到完美排列

i-3 i-2 i-1 i

X 0 1 1 这种情况下 f[i]=f[i-1]=f[i-2]  因为从i-1到i颜色相同 i-1和i对f[i]没做出贡献 与f[i-2]相比 f[i]既没增加也没减少 

X 1 1 1 这种情况下f[i]=f[i-2]  因为从i-2到i颜色相同 i-1和i对f[i]没做出贡献 与f[i-2]相比 f[i]既没增加也没减少

所以f[i]=f[i-1]+f[i-2]

不完美的就是2^n-f[i]

Orz

转载地址：https://blog.csdn.net/li412302070/article/details/12848369 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！