City Destruction Kattis

/**
题目：City Destruction Kattis - city
链接：https://vjudge.net/problem/Kattis-city
题意：有n个怪兽，排成一行。每个怪兽有一个生命值和一个爆炸值。每次可以选择一个怪兽攻击早造成d伤害。
如果生命值<=0；那么怪兽i死亡并且爆炸。i+1,i-1第怪兽都会受到
第i个怪兽的爆炸值伤害。如果第i-1被第i炸死，第i-1怪兽不会继续炸别人。
不会传递。也就是只有攻击者攻击致死的怪兽才会对i-1，i+1造成爆炸值伤害。
求最少攻击多少次才能杀死所有的怪兽。
思路：
定义dp[i][j]表示前i个怪兽，j=0表示i-1比i先死，j=1表示i-1比i后死需要的最少攻击次数。
///本题直接写递推方程我写不出来，因为i和i-1以及未知的i+1都有关联。i+1是未知的。
所以不好表示，本人菜鸡。如果dfs记忆化做法，倒是清晰。

*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <iostream>
#include <vector>
using namespace std;
#define ms(x,y) memset(x,y,sizeof x)
typedef long long LL;
const int N = 1e4;
const LL INF = 1e18;
LL dp[N][2];///j=0表示i-1比i先死，j=1表示i-1比i晚死。
int h[N], e[N];
int n, d;
LL cal(LL r)
{
    if(r<=0) return 0;
    if(r%d==0){
        return r/d;
    }
    return r/d+1;
}
LL dfs(int i,int j)
{
    if(i==n){
        return 0;
    }
    LL &res = dp[i][j];
    if(res!=-1) return res;
    res = INF;
    LL r = h[i];
    if(j==0){
        r -= e[i-1];
        res = min(res,dfs(i+1,0)+cal(r));
        if(i<n-1){
            res = min(res,dfs(i+1,1)+cal(r-e[i+1]));
        }
    }else
    {
        res = min(res,dfs(i+1,0)+cal(r));
        if(i<n-1){
            res = min(res,dfs(i+1,1)+cal(r-e[i+1]));
        }
    }
    return res;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&d);
        for(int i = 0; i < n; i++){
            scanf("%d",&h[i]);
        }
        for(int i = 0; i < n; i++){
            scanf("%d",&e[i]);
        }
        memset(dp, -1, sizeof dp);
        printf("%lld
",dfs(0,1));
    }
    return 0;
}