antivenom's blog

How can i construct a DP solution for this question????
By antivenom, 9 years ago, In English

Hello,After seeing this question the first thing came to my mind was Dynamic programming.I tried constructing a solution but could not make it,maybe because i don't have that much of experience.

  #include <bits/stdc++.h>
  using namespace std;
  int main() 
  {
      int n,m,a,b; 
      cin>>n>>m>>a>>b;
      int final=0,dp[n+1];
      dp[0]=0;
      for(int i=1;i<=n;i++)
	 dp[i]=min(dp[i-1]+a,dp[i-m]+b);
      cout<<dp[n];
      return 0;
 }

P.S:I know it can be solved without using Dp,but i request you to give Dp approach if it is possible.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
9 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

for i =  1 ... m - 1 dp[i - m] is undefined.

you may have WA in cases when prefered buy the special ticket for more than n rides.

correct solution

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if(i>=m) dp[i] = min(dp[i-1]+a,dp[i-m]+b); else dp[i]=min(dp[i-1]+a,b);

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After putting your condition it fails on testcase 8.Before that it used to fail on 3.So some improvement is there.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      My solution Got accepted lol

      Link Can you post a link of your solution ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Bingo!!!Correct answer!!!...Please explain me else part of the recursion :)

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it 
          With a ticket for 'm' rides, you can travel m times or less.

          Lets take this example : 7 5 5 1 Here the minimum cost for travelling 1...5 times is 1 . so DP[1...5] should have a value of 2.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            can you explain the second test case 5 2 2 3 how the answer is 8?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Sure . Split 5 rides into 2 rides + 2 rides + 1 ride .
              The cost for 2 rides = 3 and the cost for 1 ride = 2.

              So you get 3+3+2 = 8

              → Reply