Advertisement
Guest User

Untitled

a guest
Jan 21st, 2020
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.12 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MX = 1e5+5;
  4. int n, cost1[MX], cost2[MX], change1[MX], change2[MX];
  5. long long dp[MX][3];
  6.  
  7. long long solve(int ind, int last){
  8. if(ind == n) return 0;
  9. if(dp[ind][last] != -1) return dp[ind][last];
  10. long long ans = 0;
  11. if(!last){
  12. ans = min(ans, solve(ind+1,1) + cost1[ind]);
  13. ans = min(ans, solve(ind+1,2) + cost2[ind]);
  14. }
  15. else if(last == 1){
  16. ans = min(ans, solve(ind+1,1) + cost1[ind]);
  17. ans = min(ans, solve(ind+1,2) + cost2[ind] + change1[ind]);
  18. }
  19. else if(last == 2){
  20. ans = min(ans, solve(ind+1,2) + cost2[ind]);
  21. ans = min(ans, solve(ind+1,1) + cost1[ind] + change2[ind]);
  22. }
  23. return dp[ind][last] = ans;
  24. }
  25.  
  26. int main(){
  27. int t;
  28. cin>>t;
  29. while(t--){
  30. cin>>n;
  31. for(int i = 0 ; i < n ; i++) cin>>cost1[i];
  32. for(int i = 0 ; i < n ; i++) cin>>cost2[i];
  33. for(int i = 1 ; i < n ; i++) cin>>change1[i];
  34. for(int i = 1 ; i < n ; i++) cin>>change2[i];
  35. memset(dp, -1, sizeof dp);
  36. cout<<solve(0,0)<<endl;
  37. }
  38. return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement