Cut ribben codeforces

#1

https://codeforces.com/contest/189/problem/A

please tell me the bottom up do code for this question

#2

Hey @ankit_verma
refer to this : https://codeforces.com/contest/189/submission/17217154

#3


what mistake in this code, i don’t understand why in the actual solution that is running 3 different loop then return…

#4

Hey @ankit_verma
Here did 2 changes in ur code

#include <bits/stdc++.h> 
using namespace std;
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

#define forr(i,x,y) for(int i=x; i<y; i++)    
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
//#define 2dDP(m,n,k) vector<vector<int> > dp(m,vector <int> (n,k));


 
int32_t main()
{
    IOS;
    int t=1;
    //cin>>t;
    
    while(t--){
        int n;
        cin>>n;
        int a[3];
        forr(i,0,3) cin>>a[i];
        vi dp(n+1,0);
        if(a[0]<=n)dp[a[0]]=1;  //added this statements
        if(a[1]<=n)dp[a[1]]=1;
        if(a[2]<=n)dp[a[2]]=1;
        forr(i,1,n+1){
            for(int j=0;j<3;j++)
            if(i-a[j]>=0){
                if(dp[i-a[j]]==0)continue; //added this
                dp[i]=max(1+dp[i-a[j]],dp[i]);
            }
        }
        cout<<dp[n];
    }
}

Otherwise Say one of a,b,c is 3 and its minimum
then dp[4]=max(dp[4],do[4-3]+1) =1
But we cant form anycuts here
So I think this is where u were going wrong so corrected that

1 Like
#5

if(dp[i-a[j]]==0)continue;

why added this??

#6

This makes sure that if we cant create i-a[j] then we also cannot create i from it by making a ut of a[j]
Like in above example
Since dp[1] is 0 so hence we cant make dp[4] as well

1 Like
#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.