【u240】棋子放置

2019-11-08 18:29:10

字體：大中小

來源：轉載

供稿：網友

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。

【輸出格式】

一行，方案總數。

【數據規?！?/p>

Sample Input1

2 Sample Output1

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)