ybtoj dp T2恐狼后卫

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1e3+7;
int n,atk;
int a[N],b[N],h[N],times[N],f[N][N];
signed main(){
    scanf("%lld%lld",&n,&atk);
    cerr<<n<<" "<<atk<<" ";
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&a[i],&b[i],&h[i]);
        cerr<<a[i]<<" "<<b[i]<<" "<<h[i]<<" ";
        // h[i]--;
    }
    for(int i=1;i<=n;i++){
        int x=(int)ceil((h[i]+atk-1)/atk);//防止不小于0
        // printf("需要%d次\n",x);
        times[i]=x;f[i][i]=x*(a[i]+b[i+1]+b[i-1]);
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            f[l][r]=0x3f3f3f3f;
            for(int k=l;k<=r;k++){
                int cost=times[k]*(a[k]+b[l-1]+b[r+1]);
                f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+cost);
            }
        }
    }
    printf("%lld",f[1][n]);
    return 0;
}