生活随笔
收集整理的這篇文章主要介紹了
UVa 10359 - Tiling
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
題目：給你一個(gè)2*n的地面，用1*2和2*2的地板磚鋪滿，有多少種不同方案。
分析：組合數(shù)學(xué)，動(dòng)態(tài)規(guī)劃。直接找到地推關(guān)系求解。
? ? ? ? ? ? 因?yàn)?#xff0c;只可能是最后一列是一個(gè)整體（1種情況）或者最后兩列是一個(gè)整體（兩種情況）；
? ? ? ? ? ? 所以，有遞推公式：f（n）= f（n-1）+ 2*f（n-2）；
? ? ? ? ? ? 可以使用動(dòng)態(tài)規(guī)劃或母函數(shù)（an = （pow（2，n+1）-pow（-1，n+1））/ 3）求解。
說(shuō)明：大整數(shù)運(yùn)算，這里采用dp求解，貌似快速冪會(huì)快點(diǎn)╮(╯▽╰)╭。
[cpp]?view plaincopyprint?
#include?<algorithm>?? #include?<iostream>?? #include?<cstdlib>?? #include?<cstring>?? #include?<cstdio>?? #include?<cmath>?? ?? using?namespace?std;?? ?? int?ans[255][101],two[101];?? ?? void?copy_array(int?*a,?int?*b)?? {?? ????for?(int?i?=?0;?i?<?100;?++?i)?? ????????a[i]?=?b[i];?? }?? ?? void?add_array(int?*c,?int?*a,?int?*b)?? {?? ????for?(int?i?=?0;?i?<?100;?++?i)?? ????????c[i]?=?0;?? ????for?(int?i?=?0;?i?<?100;?++?i)?{?? ????????c[i]?+=?a[i]+b[i];?? ????????if?(c[i]?>?9)?{?? ????????????c[i+1]?+=?c[i]/10;?? ????????????c[i]?%=?10;??? ????????}?? ????}?? }?? ?? void?output_array(int?*a)?? {?? ????int?end?=?100;?? ????while?(end?&&?!a[end])?--?end;?? ????while?(end?>=?0)?printf("%d",a[end?--]);?? ????printf("\n");?? }?? ?? int?main()?? {?? ????memset(ans,?0,?sizeof(ans));?? ????ans[0][0]?=?1;ans[1][0]?=?1;?? ????for?(int?i?=?2;?i?<?252;?++?i)?{?? ????????add_array(two,?ans[i-2],?ans[i-2]);?? ????????add_array(ans[i],?ans[i-1],?two);?? ????}?? ?????? ????int?n;?? ????while?(~scanf("%d",&n))?? ????????output_array(ans[n]);?? ?????? ????return?0;?? } ?
總結(jié)
以上是生活随笔為你收集整理的UVa 10359 - Tiling的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
