Блог пользователя himanshu1212

Jump from one array element to another
Автор himanshu1212, история, 4 года назад, По-английски

Could anyone please send the code for this problem?

You are given an array of N integers. You have to find the minimum cost that is required to cross the array by jumping from one element to another. You need to start from the first element of the array and you can jump in both directions,but length of forward jump must be 2 and backward jump must be 1.

The cost of forward and backward jump is the value of the element from which you are jumping.,that is the cost of jumping from i index to (i+2) and the cost of jumping from i to (i-1) index is the value of i element of the array

If you are at the last element then you can jump out of the array and cost of that jump will be the value of the last element of array A

  • Проголосовать: нравится
  • -25
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

cAN ANYONE PLEASE SEND THE CODE?

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I can understand asking for help or hints, but just asking for someone to solve the entire problem for you seems either very suspicious or very lazy.

    I'll give you the benefit of the doubt and assume that I'm interpreting things harshly. If you would like help with this problem, I'm sure plenty of people in this community would be happy to help. But you can't post a problem and expect somebody to hand you the answer.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I guess you are right! Could you please give a hint?

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Spoiler
        Spoiler
        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I can't see any way to have both backward and forward transitions without a Djikstra-esque shortest distance. Can you give an idea on how to know the DAG for this kind of DP? Here, I mean the dependency order in which to calculate.

          → Ответить
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Yeah, generally transitions going in both directions can be an issues in DP. But I think you can:

            Spoiler
            → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please see if it's correct. I have used memoization.

#include <bits/stdc++.h>
using namespace std;

static int t[10000]; 
// ...Or any maximum size of the array.

int minCost(vector<int> &A, int pos){
    if(pos > A.size()-1){
        return t[pos] = 0;
    }
    else if(t[pos] != -1){
        return t[pos];
    }
    int c1;
	if(t[pos+2] != -1){
		c1 = t[pos+2];
	}
    else{
		c1 = minCost(A, pos+2) + A[pos];
	}
	
    if(pos>0 && t[pos-1] != -1){
		int c2;
		if(t[pos-1] != -1){
			c2 = t[pos-1];
		}
		else{
        	c2 = minCost(A, pos-1) + A[pos];
		}
        return t[pos] = min(c1, c2);
    }
    else{
        return t[pos] = c1;
    }
}

int main(){
    memset(t, -1, sizeof(t));
    int N;
    cin>>N;
    vector<int> A(N);
 
 	for(int i=0; i<N; i++){
        cin>>A[i];
    }
    cout<<minCost(A, 0);
    return 0;
}
→ Ответить