递推DP URAL 1017 Staircases

题目传送门

 /*
题意:给n块砖头,问能组成多少个楼梯,楼梯至少两层,且每层至少一块砖头,层与层之间数目不能相等!
递推DP:dp[i][j] 表示总共i块砖头,最后一列的砖头数是j块的方案数
状态转移方程:dp[i][j] += dp[i-j][k] 表示最后一列是j,那么上一个状态是少了最后一列
总共i-j块砖头,倒数第二列是k块砖头。k<j, j<=i
最后累加dp[n][i], i<n因为最少要两层
dp[0][0] = 1;
还有更简单的做法,没看懂:http://m.blog.csdn.net/blog/jyysc2010/9917439
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std; const int MAXN = 5e2 + ;
const int INF = 0x3f3f3f3f;
long long dp[MAXN][MAXN];
long long ans; int main(void) //URAL 1017 Staircases
{
//freopen ("J.in", "r", stdin); int n;
while (scanf ("%d", &n) == )
{
memset (dp, , sizeof (dp)); dp[][] = ;
for (int i=; i<=n; ++i)
{
for (int j=; j<=i; ++j)
{
for (int k=; k<j; ++k)
{
dp[i][j] += dp[i-j][k];
}
}
} ans = ;
for (int i=; i<n; ++i) ans += dp[n][i];
printf ("%I64d\n", ans);
} return ;
}
上一篇:Java集合-LinkedList源码分析


下一篇:jQuery操作列表数据转成Json再输出为html dom树