题目描述:
Maoge有N个砖块 (2<=N<=1000), 他想要把这些砖块搭成一个塔。如果他把砖块A放在B上面，A的长度必须小于等于B的长度减去D (1<=D<=n)。请找出一共有有多少种方法，然后输出答案 mod 10^9+7。
塔的高度不能为零。
输入格式：
第一行两个整数N和D。
第二行N个整数，代表砖块的长度。
输出格式:
答案 modulo 10^9+7.
样例输入:
4 1 1 2 3 100
样例输出:
15
4 个赞
∵本题N有1000多
∴首用递推
很简单，按题意即可
关键代码：
sort(a+1,a+n+1);//排序很重要
for(int i=1;i<=n;i++){
s[i]=1;///初始化
for(int j=1;j<i;j++){
if(a[i]-a[j]>=d) s[i]=(s[i]+s[j])%M;//递推式（状态转移方程）
}
ans=(ans+s[i])%M;
}
2 个赞