Ural 1017 The Staircases

DP  状态转移方程:f[i][j]=f[i-1][j]+f[i-1][j-i]
//
Ural 1017
#include<iostream>
using namespace std;
const int MAX=505;
long long f[MAX][MAX]={0}; 
 
//f[i][j]表示最后一个阶梯的高度不超过i,使用j个bricks的方案  f[i][j]=f[i-1][j]+f[i-1][j-i] 
int main()
{
    
int n,i,j;
    cin
>>n;
    f[
0][0]=1;
    
for(i=1; i<=n; i++)
    {
    
for(j=n; j>=i; j--)
             f[i][j]
=f[i-1][j]+f[i-1][j-i];
    
for(j=0; j<=i-1; j++)
             f[i][j]
=f[i-1][j];
    }
    cout
<<f[n][n]-1<<endl;
    
    
//system("pause");
}

posted on 2010-06-20 21:43 田兵 阅读(178) 评论(0)  编辑 收藏 引用 所属分类: URAL


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜