antivenom's blog

How can i construct a DP solution for this question????
By antivenom, 11 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?
»
11 years ago, hide # |
← 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
»
11 years ago, hide # |
 
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