第一眼看出来是动归，然后想到了一个o(n3)的算法。。
到网上一看我凌乱了。。Orz n2帝，Orz压维帝。。。
n3就不说了。。伤心
说说n2算法
f[i][j]表示用i块砖最后一列不超过j的情况数，那么f[i][j]=f[i][j-1]+f[i-j][j-1];
因为j只与j-1有关，所以可以把j放到第一维，然后压掉。。
对于压维可能产生的后效，跟01背包一样，第二重循环倒着来就OK。
有个地方要注意。。就是要用INT64。。不然别怪我为什么不告诉你WA是什么感
#include<stdio.h>
long n,j,i;
__int64 f[500];
int main()
{
scanf("%d",&n);
f[0]=1;
for (j=1;j<=n;j++)
{
for (i=n;i>=j;i--)
f[i]=f[i]+f[i-j];
}
printf("%I64d",f[n]-1);
}
觉
posted on 2011-06-27 20:12
梦转千寻 阅读(76)
评论(0) 编辑 收藏 引用