Similar to Coin Change II Problem

programming
Tags: #<Tag:0x00007f1827ad47b0>

#1

Just think like, Coin Change II problem.


#include <bits/stdc++.h>
using namespace std;
#include <chrono> 
#ifndef mehul
#pragma GCC optimize("Ofast")
#endif

typedef long long ll;
typedef unordered_map<int, int> umapii;
typedef unordered_map<int, bool> umapib;
typedef unordered_map<string, int> umapsi;
typedef unordered_map<string, string> umapss;
typedef map<string, int> mapsi;
typedef map<pair<int, int>, int> mappiii;
typedef map<int, int> mapii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef unordered_set<int> useti;

#define debug(x) cout << '>' << #x << ':' << x << endl;
#define uset unordered_set
#define it iterator
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second

#define INF 4557430888798830399ll
#define MOD 1000000007
#define EPS 1e-7
#define PI acos(-1)


#define sz(x) (int)(x).size()
 
#define fr(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define frr(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define trav(a, x) for(auto& a : x)
#define fil(ar, val) memset(ar, val, sizeof(ar))  // 0x3f for inf, 0x80 for -INF can also use with pairs


int Solution::solve(const vector<int> &A, const vector<int> &B, const vector<int> &C) {
	int a = A.size();
	int b = B.size();
	int c = C.size();
	
	int mfc = *max_element(all(A));

	vector<vector<int>>dp(mfc+1, vector<int>(b, 0));
	//Fill for j = 0 ---> when only till dish 1;
	fr(i,1, mfc){
		if (i%B[0]!=0)
		{
			dp[i][0] = INT_MAX;
		}else{
			dp[i][0] = C[0]*(i/B[0]);
		}
	}
	//fill from 1, 1 to mfc, b
	fr(i, 1, mfc){
		fr(j, 1, b-1){
			int v1 = dp[i][j-1];
			int v2 = (i-B[j]>=0 && dp[i-B[j]][j]!=INT_MAX)?(dp[i-B[j]][j]+C[j]):(INT_MAX);
			dp[i][j] = min(v1, v2);
		}
	}

	int ans = 0;
	rep(i, a){
		ans+=dp[A[i]][b-1];
	}

	return ans;

}