首页 > 代码库 > hdu1992(递推)

hdu1992(递推)

2024-08-06 21:18:33   223人阅读

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1992

题意：用1*2和2*1的小长方形铺垫4*W的方格有多少种方法。

分析：假如新加入1列，这列都竖着，肯定有a[i]种，假如最后加入的方块要横跨最右那条边界，没有横跨到倒数第二列，则有4*a[i-2];当同时横跨最右的两条边界，没有跨倒数第三条边界，则有2*a[i-3]种，当横跨同时最后三条时，没有跨倒数第四条边界时，模拟发现有3*a[i-4]种，即当同时横跨奇数t条边界时，则有2*a[i-t];t为偶数时有3*a[i=t];所以发现a[i]=a[i-1]+4*a[i-2]+2*a[i-3]+3*a[i-4]+......+a[i-i]*b(i为奇数b=2，为偶数b=3).

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010using namespace std;LL a[1010];void init(){    a[0]=1;a[1]=1;a[2]=5;a[3]=11;    for(int i=4;i<=30;i++)    {        LL sum=a[i-1]+4*a[i-2];        LL b=2;        for(int j=i-3;j>=0;j--)        {            sum+=a[j]*b;            if(b==2)b++;            else b--;        }        a[i]=sum;    }}int main(){    int t,n,cas=1;    init();    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        printf("%d %I64d\n",cas++,a[n]);    }}
View Code

 

hdu1992(递推)


联系
我们