首页 > 代码库 > HDU 1041 Computer Transformation 数学DP题解
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; }
HDU 1041 Computer Transformation 数学DP题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。