腾讯笔试第五题，让我有了新发现。
开始做这道题，一直卡在50%样例那里，最开始没有mod通知，50%后面应该是答案为负数了。后面加了mod后，50%提示超时，改了多久都没改过来，最后20s，我改了两行代码，就直接ac了。
如图，就改了求和的代码，将第一个圈的代码，改成了第二个圈的写法，就不超时了，真的是发现了新大陆啊。
附ac代码，代码写的乱，不要吐槽我。解题思路就是：
假设k=2，dp[i]表示i朵花的放法，如果k=2，i=3；
则末尾结束的花有两种： **红，*白白，即dp[i] = dp[i-1]+dp[i-k]，前提是i-k要>=0，否则不加dp[i-k];
后面算个sum总数就行。
package leetcode.tencent9_1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.Scanner;
/**
* P5
* create by chenshihang on 2019/9/1
*/
public class P5 {
static long mod = 1000000007;
static long[] dp = new long[100005];
static int k;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int n = in.nextInt();k = in.nextInt();
int a,b;
initDp(100004);
for(int i=0;i<n;i++){
a = in.nextInt();
b = in.nextInt();
m1(a,b);
}
}
public static void initDp(int n){
if(k==0){
//特殊处理；都为1;
for(int i=0;i<=n;i++){
dp[i]=1;
}
return;
}
dp[0]=1;
if(k==1){
dp[1]=2;
dp[2]=4;
} else {
dp[1]=1;
if(k>2){
dp[2]=1;
}else {
dp[2]=2;
}
}
for(int i=3;i<=n;i++){
dp[i]+=dp[i-1];
dp[i]%=mod;
if(i-k>=0){
dp[i]+=dp[i-k];
dp[i]%=mod;
}
}
}
public static void m1(int ai,int bi){
int i;
long sum = 0;
for(i=ai;i<=bi;i++){
// sum = (sum+dp[i])%mod;
sum = sum+dp[i];
if(sum>=mod){
sum%=mod;
}
}
System.out.println(sum);
}
}
投递金山WPS等公司10个岗位 >
