핵심 아이디어

<aside> 💡

$dp_{ie} = i$일까지 진행했고 배터리 잔량이 $e$일때 최소 비용

$i$일에 충전을 한 경우, 하지 않은 경우를 나눠서 전이하면 된다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;

int N, B, C;

int P[1'001];
ll F[1'001];
int D[1'001];

ll dp[1'001][1'001];

ll go(int i, int e)
{
    ll &ret = dp[i][e];
    if(ret != -1) return ret;
    
    ll cur = ll(1e+18);

    if(e+D[i-1]<=C){
        ll prv = go(i-1, e+D[i-1]);
        if(prv != -2) cur = prv;
    }
    if(0<=e-P[i-1]){
        ll prv = go(i-1, e-P[i-1]);
        if(prv != -2) cur = min(cur, prv+D[i-1]*F[i-1]);
    }
    if(e == C){
        for(int k = max(0, C-P[i-1]); k<=C; k++){
            ll prv = go(i-1, k);
            if(prv != -2) cur = min(cur, prv+D[i-1]*F[i-1]);
        }
    }

    if(cur == ll(1e+18)) return ret = -2;
    else return ret = cur;
}

void solve()
{
    cin >> N >> B >> C;
    for(int i = 0; i<N; i++) cin >> P[i];
    for(int i = 0; i<N; i++) cin >> F[i];
    for(int i = 0; i<N; i++) cin >> D[i];

    memset(dp, -1, sizeof(dp));
    for(int e = 0; e<=C; e++){
        if(e == B) dp[0][e] = 0;
        else dp[0][e] = -2;
    }

    ll ans = 1e+18;
    for(int i = B; i<=C; i++){
        ll cur = go(N, i);
        if(cur != -2) ans = min(ans, cur);
    }
    cout << ans <<"\\n";
}

signed main()
{
    FASTIO;
    int _tc; cin >> _tc;
    while(_tc--) solve();    
    return 0;
}