Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MX = 1e5+5;
- int n, cost1[MX], cost2[MX], change1[MX], change2[MX];
- long long dp[MX][3];
- long long solve(int ind, int last){
- if(ind == n) return 0;
- if(dp[ind][last] != -1) return dp[ind][last];
- long long ans = 0;
- if(!last){
- ans = min(ans, solve(ind+1,1) + cost1[ind]);
- ans = min(ans, solve(ind+1,2) + cost2[ind]);
- }
- else if(last == 1){
- ans = min(ans, solve(ind+1,1) + cost1[ind]);
- ans = min(ans, solve(ind+1,2) + cost2[ind] + change1[ind]);
- }
- else if(last == 2){
- ans = min(ans, solve(ind+1,2) + cost2[ind]);
- ans = min(ans, solve(ind+1,1) + cost1[ind] + change2[ind]);
- }
- return dp[ind][last] = ans;
- }
- int main(){
- int t;
- cin>>t;
- while(t--){
- cin>>n;
- for(int i = 0 ; i < n ; i++) cin>>cost1[i];
- for(int i = 0 ; i < n ; i++) cin>>cost2[i];
- for(int i = 1 ; i < n ; i++) cin>>change1[i];
- for(int i = 1 ; i < n ; i++) cin>>change2[i];
- memset(dp, -1, sizeof dp);
- cout<<solve(0,0)<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement