maoge有N(2<=N<=1000)块砖,要搭一个塔,要求:如果砖A在砖B上面,那么A不能比B的长度-D(1<=D<=n)要长。问有几种方法,输出 答案 mod 1000000007的值。
注意,塔的高度不能为0。
【输入格式】
第一行: N,D 第二行: N个数,表示每块砖的长度,保证为正整数且小于等于10000。
【输出格式】
方案数,输出要mod 1000000007。
【样例输入】
4 1
1 2 3 100
【样例输出】
15
总共就通过一个,错在哪?
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std;
int n,d;
int num[1001];
int top=0;
long long ans=1;
long long b[1001];
int main(){
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
sort(num+1,num+1+n);
b[1] =1;
for(int i=2;i<=n;i++)
{
top=1;
while(num[top]<=num[i]-d && top<i){
b[i]+=b[top];
b[i]%=mod;
top++;
}
b[i]+=top;
b[i]%=mod;
}
if(b[n]<n) b[n]+=n-1;
cout<<b[n]%mod;
}
#include <iostream>
#include <algorithm>
using namespace std;
const int M=1000000007;
int a[1005],s[1005];
int main() {
int n,d,ans=0;
cin>>n>>d;
for(int i=1;i<=n;i++) cin>>a[i];
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;
}
cout<<ans<<endl;
return 0;
}