Problem : UVa 10313 - Pay the Price
Here dp[i][j][k] means --:
"i" -- The last coin used
"j" -- Total sum obtained
"k" -- "No. of coins taken"
It can be calculated as:
dp[i][j][k]=dp[i-1][j][k]+dp[i][j-i][k-1].
where 1st condition is (when "i"th coin is not taken) and "2"nd condition is (when "i"th coin is taken so subtracting its value from sum-"j" and decreasing "k" as one coin is used.).It can be calculated by both Bottom-up Approach and Top-down Method just need a little optimisation to pass under the given constraints..
*Take care of corner cases like n=0 because there is 1 way to get 0 using 0 coins so::
Input :
0
0 0
0 1
0 0 0
0 0 1
0 1 1
0 1 2
200 30 75
Output:
1
1
1
1
1
0
0
2347163627458
Top-Down Method :
//\\__ hr1212 __//\\
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%lld\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007
ll n,m,dp[400][400][400];
char s[400];
ll solve(ll i,ll j,ll k){
if(j==0 && k==0)
return 1;
if( i<1 || j<1 || k<=0)
return 0;
if(dp[i][j][k]!=-1)
return dp[i][j][k];
return dp[i][j][k]=solve(i-1,j,k)+solve(i,j-i,k-1);
}
int main(){
ll r,k,i,c=0,st,x=0,y=0,j,t,l,z,x1=0,y1=0,l1,l2;
ll ans=0;string p,q[5];
// dp is cleared only once so previous values are automatically taken from dp and only new values are computed again otherwise would result in TLE.
clr(dp,-1);
while(gets(s)){
z=sscanf(s,"%lld %lld %lld",&n,&l1,&l2);
ans=0;
if(z==1){
f(i,1,min(n+1,301LL))
ans+=solve(n,n,i);
if(n==0)
ans=1;
}
else if(z==2){
f(k,1,min(l1+1,301LL))
ans+=solve(n,n,k);
if(n==0)
ans=1;
}
else{
f(k,l1,min(l2+1,301LL))
ans+=solve(n,n,k);
if(n==0 && l1==0)
ans=1;
}
pi(ans);
}
return 0;
}
Bottom-Up Approach :
//\\__ hr1212 __//\\
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%lld\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007
ll n,m,dp[400][400][400];
char s[300];
int main(){
ll r,k,i,c=0,st,x=0,y=0,j,t,l,z,x1=0,y1=0,l1,l2;
ll ans=0;string p,q[5];
for(k=0;k<=300;k++){
for(j=0;j<=300;j++){
for(i=0;i<=300;i++){
if(j==0 && k==0 && i!=0)
dp[i][j][k]=1;
else if(i==0 || j==0 || k==0)
dp[i][j][k]=0;
else{
dp[i][j][k]=dp[i-1][j][k];
if(j-i>=0 && k-1>=0)
dp[i][j][k]+=dp[i][j-i][k-1];
}
}
}
}
// 1D range sum is used to sum the result where dp[i][i][k] is the total ways to obtain sum "i" using "k" or less coins.
for(i=1;i<=300;i++)
for(j=1;j<=300;j++)
dp[i][i][j]+=dp[i][i][j-1];
while(gets(s)){
z=sscanf(s,"%lld %lld %lld",&n,&l1,&l2);
ans=0;
if(z==1){
z=min(n,300LL);
ans=dp[n][n][z];
if(n==0)
ans=1;
}
else if(z==2){
z=min(l1,300LL);
ans=dp[n][n][z];
if(n==0 && l1<=1)
ans=1;
}
else{
z=min(l2,300LL);
y=max(l1-1,0LL);
ans=dp[n][n][z]-dp[n][n][y];
if(n==0 && l1==0)
ans=1;
}
pi(ans);
}
return 0;
}
No comments:
Post a Comment