POJ2806 Square

题目描述

给定\(2*1\)和\(2 * 2\)两种规格的地砖，请问\(2 * n\)的地面总共有多少种方法?

下面是铺满\(2*17\)的地面的示意图。

输入输出格式

输入

多组数据，每组数据包括1行1个整数n，表示地面的长度。\((0\leq n \leq250)\)

输出

每组数据输出\(1\)行\(1\)个整数，表示铺满\(n\)米地面的方法数。

思路

因为我们知道长度为\(i\)的矩阵只能由\(i-1\)和\(i-2\)变来，又长度为一的矩阵的方法数为\(1\)，长度为二的矩阵的方法数为\(3\)，其中有一种相当于\(i-1\)的方法数，所以状态转移方程为\(dp[i][j]=dp[i-1][j]+dp[i-2][j]*2;\)

代码

#include<bits/stdc++.h>

using namespace std;

int dp[301][501];  //dp[i]用来存储第i列的结果，dp[i][0]存储长度

int main(){

    dp[1][0]=1;

    dp[1][1]=1;

    dp[2][0]=1;

    dp[2][1] = 3;

    for(int i=3;i<=300;i++){

		int len=max(dp[i-2][0],dp[i-1][0]);

        for(int j=1;j<=len;j++)

			dp[i][j]=dp[i-1][j]+dp[i-2][j]*2;  //按位加

        dp[i][0]=max(dp[i-2][0],dp[i-1][0]);   //取两个加数中较长的长度

        for(int j=1;j<=dp[i][0];j++){

            dp[i][j+1]+=dp[i][j]/10;  //进位

            dp[i][j]%=10;

        }

        while(dp[i][dp[i][0]+1]>0){ //更新高精度加法结果的位数

            dp[i][0]++;

            dp[i][dp[i][0]+1]+=dp[i][dp[i][0]]/10;

        }

    }

    int n;

    while(cin>>n){

        if(n==0)

            cout<<1<<endl;

        else{

            for(int i=dp[n][0];i>=1;i--)

            	cout<<dp[n][i];

            cout<<endl;

        }

    }

	return 0;

}

巴特西

POJ2806 Square

题目描述

输入输出格式

输入

输出

思路

代码

最新文章

热门文章