Light OJ 1169 / DP

/***
 created: 2022-08-28-13.37.36
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll a[2][10005],n;
ll dp[2][10005];
ll f1[2][20005];

ll solve(ll in ,ll fl)
{
    if(in==n) return 0;
    if(dp[fl][in]!=-1) return dp[fl][in];
    ll ans=INT_MAX;
    ans=min(solve(in+1,fl)+a[fl][in] , solve(in+1,fl^1)+f1[fl][in]+a[fl][in]);
    return dp[fl][in]=ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        ll i,j,k,l;

        cin>>n;

        memset(dp,-1,sizeof dp);

        for(i=0;i<2;i++)
        {
            for(j=0;j<n;j++)
            {
                cin>>a[i][j];
            }
        }

        for(i=0;i<2;i++)
        {
            for(j=0;j<n-1;j++)
            {
                cin>>f1[i][j];
            }
        }

        ll ans=solve(0,0);
        memset(dp,-1,sizeof dp);
        ans=min(ans,solve(0,1));

        cout<<"Case "<<cs<<": "<<ans<<nl;
    }
    get_lost_idiot;
}