首页 > 代码库 > [hdu1023]递推
[hdu1023]递推
http://acm.hdu.edu.cn/showproblem.php?pid=1023
如果把栈里面的元素个数表示成状态，每一步（共2 * n步）的状态构成的状态序列的种数就是答案，令dp[i][j]表示第i步栈的状态为j的方案数，则有：
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]，+1、-1相当于进栈和出栈，需考虑边界条件，详见代码（答案太大，需用大数）：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <map> 7 #include <stack> 8 #include <string> 9 #include <ctime> 10 #include <queue> 11 #define mem0(a) memset(a, 0, sizeof(a)) 12 #define mem(a, b) memset(a, b, sizeof(a)) 13 #define lson l, m, rt << 1 14 #define rson m + 1, r, rt << 1 | 1 15 #define eps 0.0000001 16 #define lowbit(x) ((x) & -(x)) 17 #define memc(a, b) memcpy(a, b, sizeof(b)) 18 #define x_x(a) ((a) * (a)) 19 #define LL __int64 20 #define DB double 21 #define pi 3.14159265359 22 #define MD 10000007 23 #define INF (int)1e9 24 using namespace std; 25 struct BigNum{ 26 #define maxlen 10 27 #define memc(a, b) memcpy(a, b, sizeof(b)) 28 #define mem0(a) memset(a, 0, sizeof(a)) 29 typedef __int64 Num[maxlen + 2]; 30 Num num; 31 char s[maxlen + 2]; 32 BigNum operator+(BigNum num2) { 33 BigNum ans; 34 mem0(ans.num); 35 for(int i = 1; i <= maxlen; i++) { 36 ans.num[i] += num[i] + num2.num[i]; 37 ans.num[i + 1] += ans.num[i] / (int)1e9; 38 ans.num[i] %= (int)1e9; 39 } 40 return ans; 41 } 42 BigNum operator*(BigNum num2) { 43 BigNum ans; 44 mem0(ans.num); 45 for(int i = 1; i <= maxlen; i++) { 46 for(int j = 1; j <= maxlen; j++) { 47 if(i + j - 1 <= maxlen) { 48 ans.num[i + j - 1] += num[i] * num2.num[j]; 49 ans.num[i + j] += ans.num[i + j - 1] / (int)1e9; 50 ans.num[i + j - 1] %= (int)1e9; 51 } 52 } 53 } 54 return ans; 55 } 56 void convert() { 57 int len = strlen(s), cnt = 0; 58 for(int i = len - 1; i >= 0; i -= 9) { 59 int p = 0, x = 0, t = 1; 60 while(i - p >= 0 && p < 9) { 61 x += t * (s[i - p] - ‘0‘); 62 p++; 63 t *= 10; 64 } 65 num[++cnt] = x; 66 } 67 } 68 void inp() { 69 mem0(num); 70 scanf("%s", s); 71 convert(); 72 } 73 void outp() { 74 int p = 1; 75 for(int i = maxlen; i >= 1; i--) { 76 if(num[i]) { 77 p = i; 78 break; 79 } 80 } 81 cout<< num[p]; 82 while(--p) { 83 int a[9] = {0}, x = num[p]; 84 for(int i = 0; i < 9; i++) { 85 a[i] = x % 10; 86 x /= 10; 87 } 88 for(int i = 8; i >= 0; i--) { 89 printf("%d", a[i]); 90 } 91 } 92 } 93 BigNum(char str[]) { 94 strcpy(s, str); 95 mem0(num); 96 convert(); 97 } 98 BigNum(){} 99 };100 BigNum f[220][120];101 int main()102 {103 //freopen("input.txt", "r", stdin);104 //freopen("output.txt", "w", stdout);105 int n;106 while(~scanf("%d", &n)) {107 mem0(f);108 f[0][0] = BigNum("1");109 for(int i = 1; i <= 2 * n; i++) {110 for(int j = 0; j <= n; j++) {111 f[i][j] = f[i - 1][j + 1];112 if(j) f[i][j] = f[i][j] + f[i - 1][j - 1];113 }114 }115 f[2 * n][0].outp();116 cout<< endl;117 }118 return 0;119 }
[hdu1023]递推
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。