来自"NOCOW"

简单的背包问题

#include<stdio.h>
double f[501]={0};
int main()
{
	long n,i,j;
	f[0]=1;
	scanf("%ld",&n);
	for (i=1;i<n;i++)
	  for(j=n-1;j>=0;j--)
	  if (i+j<=n)
	    f[i+j]+=f[j];
        printf("%.0lf",f[n]);
	return 0;
}
//by rzhpp

这道题首先是DP没错,网上有很多O(n^3)的算法,这里说一个O(n^2)的DP,f[i,j]表示最后一个阶梯的高度不超过i,使用j个bricks的方案,那么转移方程就是f[i,j]=f[i-1,j]+f[i-1,j-i]; (j-i是因为,将i个bricks用来修最后一个阶梯,所以还剩j-i个bricks)

那么程序就出来了

program cao;
const
  maxn=501;
 
var
  f:array[0..maxn,0..maxn] of qword;
  a,b,c,d,e,g,h,i,j,k,l,n,m,p,q:longint;
  ans:qword;
 
begin
  f[0,0]:=1;
  read(n);
  for i:=1 to n do
  begin
    for j:=n downto i do
      f[i,j]:=f[i-1,j]+f[i-1,j-i];
    for j:=0 to i-1 do
      f[i,j]:=f[i-1,j];
  end;
  writeln(f[n,n]-1);
end.

发现空间可以降维

program cao;
const
  maxn=501;
 
var
  f:array[0..maxn] of qword;
  a,b,c,d,e,g,h,i,j,k,l,n,m,p,q:longint;
  ans:qword;
 
begin
  f[0]:=1;
  read(n);
  for i:=1 to n do
    for j:=n downto i do
      f[j]:=f[j]+f[j-i];
  writeln(f[n]-1);
end.

http://withflying.com

---

一开始想用搜索的，不过发现这是不行的，看看样例就知道了——即使输入只有500的一半不到（212），符合的情况数也有接近10^10那么大，因此，搜索一定超时，这时候，就只能想想比较快的DP了吧（要输出的信息也很少，很有DP题目的感觉）

然后就来找最优子结构了，思考到楼梯的特点有梯级数和高度这两个最主要的特点，而梯级数是在变的，因此从高度方面思考，一旦一部分楼梯的最大高度和所用砖数确定了，那么这个楼梯的构成方法数就能确定，所以以f[i,j]记录用i个砖砌成的最大高度为j的楼梯的构成方法数，根据楼梯的高度严格递减这个特点，可写出： f[i,j]=Σf[i-j,k] (k<j)，表示除去最大高度那一个梯级，剩下砖头所做的最高为k的楼梯。 边界：f[i,i]=1 f[3,2]=1 f[4,3]=1(后面两个自己画个图就知道了)

Program Ural_1017;
Var n,i,j,k:longint;
    f:array[1..500,1..500]of int64;
    q:int64;
Begin
    readln(n);
    fillchar(f,sizeof(f),0);
    for i:=1 to n do f[i,i]:=1;
    f[3,2]:=1;f[4,3]:=1;
    for i:=5 to n do
     for j:=1 to i-1 do
      for k:=1 to j-1 do
      begin
        f[i,j]:=f[i,j]+f[i-j,k];
      end;
    q:=0;
    for k:=1 to n-1 do inc(q,f[n,k]);
    writeln(q);
End.