动态规划(DP)|URAL 1017. Staircases
文章图片
【动态规划(DP)|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<推荐阅读
- 前沿论文|论文精读（Neural Architecture Search without Training）
- Book|Book Review: Foundations of Statistical Natural Language Processing
- 神经网络Neural|神经网络Neural Networks
- Trie树（动态规划）
- 斐波那契数列如何快速计算-动态规划法
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- 416.分割等和子集
- Java数据结构和算法-动态规划算法解决背包问题
- [Golang]力扣Leetcode—初级算法—动态规划—打家劫舍