本文主要是介绍URAL 1017. Staircases，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题，写出递推式就过了。用数组zrt[x][n]表示 x个方块在宽度为n的情况下的种类数。
递推式：枚举第一列的高度，然后每一列减去第一列的高度，问题就转化成了若干个zrt [ 剩下的方块数 ] [ n-1 ].
n=2时，有公式 zrt[x][2]=(x-1)/2; 然后再加上记忆化搜索就行了。
代码如下：
long long zrt[501][32];
long long f(int x,int n){if(zrt[x][n]) return zrt[x][n];if(x<0) return 0;if(n==2) return (x-1)/2;long long ANS=0;for(int i=1;;i++){//枚举第一列的高度if(x-i*n<2) break;ANS+=f(x-i*n,n-1);}return zrt[x][n]=ANS;
}
long long F(int x){int high;high=0;while(x>(high+1)*(high+2)/2) high++;long long ANS=0;for(int i=2;i<=high;i++){//枚举x个方格的宽度ANS+=f(x,i);}return ANS;
}int main(void)
{long long N;while(cin>>N){memset(zrt,0,sizeof(zrt));long long ANS=F(N);cout<<ANS<<endl;}
return 0;
}
这篇关于URAL 1017. Staircases的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
