題干：

One curious child has a set of N little bricks. From these bricks he builds different staircases. Staircase consists of steps of different sizes in a strictly descending order. It is not allowed for staircase to have steps equal sizes. Every staircase consists of at least two steps and each step contains at least one brick. Picture gives examples of staircase for N=11 and N=5:

Your task is to write a program that reads from input numbers N and writes to output numbers Q - amount of different staircases that can be built from exactly N bricks.

Input

Numbers N, one on each line. You can assume N is between 3 and 500, both inclusive. A number 0 indicates the end of input.

Output

Numbers Q, one on each line.

Sample Input
3?
5?
0?

Sample Output
1
2

解題報告：

? ?考慮動態規劃。因為具有重疊子問題和無后效性，考慮dp[i][j]代表用i塊磚塊建出最大高度為j的圖形。因為題目的限制，發現最大高度一定是最后一列，轉移就是枚舉前一列的最大高度。因為數據范圍比較小，所以n^3的算法足夠用，如果n再大一些，考慮前綴和優化一下，或者狀態的定義改變一下，改成最后一列高度小于等于j的。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 500 + 5; ll dp[MAX][MAX]; int low[MAX]; int main() {for(int i = 1; i<=500; i++) dp[i][i]=1;dp[3][2]=1;for(int i = 4; i<=500; i++) {for(int j = 1; j<=i-1; j++) {for(int k = 1; k<=j-1; k++) {if(i-j>0) dp[i][j] += dp[i-j][k];}}}int n;while(scanf("%d",&n) && n) {ll sum = 0;for(int i = 1; i<=n-1; i++) sum += dp[n][i];printf("%lld\n",sum);}return 0 ; }

代碼2：

for(int i=0; i<=n; i++) dp[0][i]=1;for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)if(i>=j)dp[i][j]=dp[i-j][j-1]+dp[i][j-1];elsedp[i][j]=dp[i][j-1];

?

總結

以上是生活随笔為你收集整理的【ZOJ - 1163】The Staircases（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。