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.
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
if(i>=m) dp[i] = min(dp[i-1]+a,dp[i-m]+b); else dp[i]=min(dp[i-1]+a,b);
After putting your condition it fails on testcase 8.Before that it used to fail on 3.So some improvement is there.
My solution Got accepted lol
Link Can you post a link of your solution ?
Bingo!!!Correct answer!!!...Please explain me else part of the recursion :)
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.
can you explain the second test case 5 2 2 3 how the answer is 8?
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