poj2506：Tiling

传送门

题目大意

用2×1与2×2的小方块去填满一个2xn的长条形区域，问有多少种填法。

思路

很标准的dp。假设当前填到第i个位置，那么能继续往后推进的办法只有三种：竖着放一个2×1的方块，或者横着放两个2×1的方块、亦或者直接放一个2×2的方块。即，dp[n]的填法直接取决于dp[n-1]与dp[n-2]。

在n-1时只有一种方法可以填，所以dp[n-1]对dp[n]的贡献就是1*dp[n-1]；在n-2时有三种方法：竖着放俩、横着放俩、放块大的，因为“竖着放俩”的方法与n-1时重叠了，所以dp[n-2]对dp[n]的贡献就是dp[n-2]*2，最终得到转移方程：

dp[n] = dp[n-1] + dp[n-2] * 2;

样例很善良的提醒了我们这题还是一个大数题目，所以用string来模拟大数加法，避免爆变量。

string add(string a, string b) {
	//维护a长于b
    if(a.length() < b.length()) swap(a,b);

    //进位值
    int up = 0;
    //自尾向头计算
    for(int i = a.length() - 1, j = b.length() - 1; i >= 0; i--, j--) {
       	a[i] = a[i] + (j >= 0 ? b[j] - '0' : 0 ) + up;
        
        int temp;
        temp = (a[i] - '0') % 10;
        up = (a[i] - '0' - temp) / 10;
        a[i] = temp + '0';

		//防止最高位进一无法储存；
        if(i == 0 && up != 0) a = "1" + a;
    }

    return a;
 }

代码

#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

int n;

string add(string a, string b) {
    if(a.length() < b.length()) swap(a,b);

    int up = 0;
    for(int i = a.length() - 1, j = b.length() - 1; i >= 0; i--, j--) {
       	a[i] = a[i] + (j >= 0 ? b[j] - '0' : 0 ) + up;
        
        int temp;
        temp = (a[i] - '0') % 10;
        up = (a[i] - '0' - temp) / 10;
        a[i] = temp + '0';

        if(i == 0 && up != 0) a = "1" + a;
    }

    return a;
 }

int main() {
	while(~scanf("%d", &n)) {
		string dp[300];
		dp[0] = dp[1] = "1", dp[2] = "3";
		for(int i = 3; i <= n; i++)
			dp[i] = add(dp[i-1], add(dp[i-2], dp[i-2]));
		cout << dp[n] << endl;
	}

	return 0;
}