HDU 1041 Computer Transformation 数学DP题解

本题假设编程是使用DP思想直接打表就能够了。

假设是找规律就须要数学思维了。

规律就是看这些连续的0是从哪里来的。

我找到的规律是：1经过两次裂变之后就会产生一个00； 00经过两次裂变之后也会产生新的00；故此须要记录好1和00出现的次数就能够递推出后面的00出现的数据了。

公式就是tbl00[i] = tbl00[i-2] + tbl1[i-2]; 当中tbl00是记录00出现的次数，tbl1是出现1出现的次数。

公式事实上是能够化简的，只是我懒得化简了。这种公式非常清楚了。

只是因为这种数极大。故此就须要用到大数运算了。

#include <stdio.h>

#include <vector>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <string>

#include <limits.h>

#include <stack>

#include <queue>

#include <set>

#include <map>

using namespace std;

const short MAX_N = 1001;

vector<short> tbl00[MAX_N], tbl1[MAX_N];//inverse saved numbers

void plusLarge(vector<short> &c, vector<short> &a, vector<short> &b)

{

	short n = (short)a.size(), m = (short)b.size(), carry = 0;

	for (short k = 0, d = 0; k < n || d < m || carry; k++, d++)

	{

		short s1 = k < n?

a[k] : 0;

		short s2 = d < m? b[d] : 0;

		carry = s1 + s2 + carry;

		c.push_back(carry % 10);

		carry /= 10;

	}

}

void genTbl()

{

	tbl00[0].push_back(0), tbl1[0].push_back(1);

	tbl00[1].push_back(0), tbl1[1].push_back(1);

	tbl00[2].push_back(1), tbl1[2].push_back(2);

	for (short i = 3; i < MAX_N; i++)

	{

		plusLarge(tbl00[i], tbl00[i-2], tbl1[i-2]);

		plusLarge(tbl1[i], tbl1[i-1], tbl1[i-1]);

	}

}

int main()

{

	genTbl();

	int n;

	while (scanf("%d", &n) != EOF)

	{

		vector<short> &a = tbl00[n];

		short m = (short)a.size();

		for (short i = m-1; i >= 0; i--)

		{

			printf("%d", a[i]);

		}

		putchar('\n');

	}

	return 0;

}