Advertisement
Josif_tepe

Untitled

Dec 15th, 2021
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int n;
  5. int dp[1010];
  6. vector<int>v;
  7. vector<int>v1;
  8. pair<int, int> backtrack[1010];
  9.  
  10. int rec(int i=0){
  11.     if(i==n){
  12.         backtrack[i] = make_pair(-1, -1);
  13.         return 0;
  14.     }
  15.  
  16.     if(dp[i]!=-1){
  17.         return(dp[i]);
  18.     }
  19.  
  20.     int result=2e9;
  21.     int sam = rec(i+1)+v[i];
  22.     int spoen = 2e9;
  23.     if(i+1<n){
  24.         spoen =  rec(i+2)+v1[i];
  25.     }
  26.     result = min(sam, spoen);
  27.     if(sam <= spoen) {
  28.         backtrack[i] = make_pair(i + 1, -1);
  29.     }
  30.     else {
  31.         backtrack[i] = make_pair(i + 2, 1);
  32.     }
  33.     dp[i]=result;
  34.  
  35.     return(result);
  36.  
  37. }
  38. int main()
  39. {
  40.  
  41.     cin>>n;
  42.  
  43.     for(int i=0; i<n; i++){
  44.         int a;
  45.         cin>>a;
  46.         v.push_back(a);
  47.  
  48.         dp[i]=-1;
  49.     }
  50.  
  51.     for(int j=0; j<n-1; j++){
  52.         int b;
  53.         cin>>b;
  54.         v1.push_back(b);
  55.     }
  56.  
  57.     rec(0);
  58.     int at =0 ;
  59.     while(at < n) {
  60.         if(backtrack[at].second == 1) {
  61.             cout << backtrack[at].first - 1 << " " << backtrack[at].first << endl;
  62.         }
  63.         at = backtrack[at].first;
  64.     }
  65.  
  66.  
  67.  
  68.     return 0;
  69. }
  70.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement