admin管理员组

文章数量:1612411
One curious child has a set of  N little bricks (5 ≤  N ≤ 500). 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 the number N and writes the only number Q — amount of different staircases that can be built from exactly N bricks.


这个题目的关键在于如何确定状态转移方程，对这个题目一开始我也是不会的。。。。。

想了数种想法，然而并没有什么卵用， 于是乎看了题解；


故请移步     http://wwwblogs/skyivben/archive/2009/03/02/1401728.html

对于待求的 n 可以先求出最小的被加数不小于1的个数再减去1就是答案

对于n个块最小加数不小于k的状况 dp[k][n] = dp[k+1][n] + dp[k+1][n-k] 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define N 510
long long dp[N][N];
int n;
int main()
{
    for(int i = 1; i <= 509; i++)
        for(int j = 1; j <= 509; j++)
        dp[i][j] = 0;
    for(int i = 1; i <= 500; i++) dp[i][i] = 1;
    for(int i = 500; i >= 1; i--)
    {
        for(int j = i+1; j <= 500; j++)
            dp[i][j] = dp[i+1][j]+dp[i+1][j-i];
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("%I64d\n",dp[1][n]-1);
    }
    return 0;
}



本文标签： URALDPStaircases

版权声明：本文标题：URAL 1017Staircases dp练习 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1728631826a1167174.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。