思路
用f[i]表示占用前i个位置并在第i个位置摆放油桶的方案数,其中f[0]肯定摆不了油桶,只有一种方案。
转移方程:1,不在第i个位置摆放油桶, f[i] += f[i-1];2,在第i个位置摆放油桶 f[i] +=f[i-k-1]。注意这里需要特判一下,如果在循环早期i-k-1<0时, 我们至少也是可以只摆一个桶的,而这也是一种方案 所以f[i] += 1
代码
import java.io.*;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = 1000010, mod = (int)1e9+7;
static long[] f = new long[N]; //f[i]表示占用前i个位置摆放油桶的方案数
public static void main(String[] args)throws IOException{
int n = nextInt(), k = nextInt();
f[0] = 1;
for(int i=1; i<=n; i++){
f[i] = f[i-1];
if(i-k-1>=0) f[i] = (f[i]+f[i-k-1])%mod;
else f[i] = (f[i]+1)%mod;
}
out.println(f[n]);
out.flush();
out.close();
}
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
}