ClumsyBot's blog

By ClumsyBot, history, 20 months ago, In English

Can someone please tell me what am i doing wrong here?

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<functional>
#include<unordered_map>
#include<numeric>

using namespace std;

#define ll long long
#define mod 1e9+7
#define cy std::cout << "YES"<< std::endl
#define cn std::cout << "NO"<< std::endl
#define IN(x) cin >> x;
#define OUT(x) cout << x;

int solve(int x,int a,int b,int c){//it gives the maximum amount of ribbon when the length is x and we have to substract the length from a,b,c
  if (x < 0)
  {
    return INT_MIN;
  }
    int len1 = solve(x-a,a,b,c)+1;
    int len2 = solve(x-b,a,b,c)+1;
    int len3 = solve(x-c,a,b,c)+1;
  return max({len1,len2,len3});
}


int main()
  {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
      freopen("input.txt","r", stdin);
      freopen("output.txt","w", stdout);
    #endif//
    int length,a,b,c;
    std::cin >> length>>a >>b >>c;
    cout << solve(length,a,b,c);

    return 0;
}
Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Have no idea, what you're trying to do, but there is some hint: in which input your solve function returns not INT_MIN?

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    base case is when the length(x) is smaller than 0. then that's invalid so i returned INT_MIN

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah, question was "When your function returns something other?"

»
20 months ago, # |
  Vote: I like it +2 Vote: I do not like it

The base case of your recursive function is incomplete. The solve() function needs to have another condition of the form "if (x == 0) return 0;". The code should work fine then.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can brute force it, I think without any DP. But for DP, i don't see in your code a base case when the ribbon can't be further cut into pieces i.e) n==0