Time Limit: 1 second Memory Limit: 128 MB
小虎刚刚上了幼儿园，老师让他做一个家庭作业：首先画3行格子，第一行有三个格子，第二行有2个格子，第三行有1个格子。 每行的格子从左到右可以放棋子，但要求除第一行外，每行放的棋子数不能超过上一行的棋子。玩了一会儿，小虎的哥哥大虎 ：这个作业有很多种摆放法，我想找到，但我不知道有多少种方案，你能帮助我吗？ 大虎是学校信息学集训队的，立刻想到用计算机来解决这个问题，并很快有了解答：13。 第二天他把问题拿到学校，并说如果第一行有N个格子，第二行有N-1个格子，…，第N行有1个格子，怎么办？现在请你一块来帮助 他解决这个难题。 数据范围： 30%数据：1<=n<=12 50%数据：1<=n<=30 100%数据：1<=n<=100
【输入格式】
仅一行，一个正整数N。
【输出格式】
一行，方案总数。
【数据规模】
Sample Input1
2 Sample Output1
4
Sample Input2
3 Sample Output2
13 【样例说明】
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u240
【题意】
【题解】 除非是最上面那一层; 否则每一行不能是空的; 设f[i][j]表示第i行第j列以下的合法方案数; 有递推公式 f[i+1][j..i+1]+=f[i][j]; 写个高精度. 最后累加f[n][1..n]就好 【完整代码】
#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int N = 110;struct bignum{ int a[N],len; bignum() { memset(a,0,sizeof a); len = 1; }};int n;bignum f[N][N];bignum jia(bignum a,bignum b){ bignum c; int &len = c.len; int lena = a.len,lenb = b.len; len = max(lena,lenb); int x = 0; rep1(i,1,len) { c.a[i] = c.a[i]+a.a[i]+b.a[i]+x; x = c.a[i]/10; c.a[i]%=10; } while (x>0) { c.a[++len] = x; x = c.a[len]/10; c.a[len]%=10; } return c;}int main(){ //freopen("F://rush.txt","r",stdin); rei(n); f[1][1].a[1] = 1; if (n>1) f[1][0].a[1] = 1; rep1(i,1,n-1) { if (i==n-1) rep1(j,1,n) f[i+1][j] = jia(f[i+1][j],f[i][0]); else rep1(j,0,i+1) f[i+1][j] = jia(f[i+1][j],f[i][0]); rep1(j,1,i) rep1(k,j,i+1) f[i+1][k] = jia(f[i+1][k],f[i][j]); } bignum ans; rep1(i,1,n) ans = jia(ans,f[n][i]); int len = ans.len; rep2(i,len,1) PRintf("%d",ans.a[i]); return 0;}新闻热点
疑难解答
