UVa 357

#include<bits/stdc++.h>
#define ll long long

using namespace std;


ll count( ll S[], ll m, ll n )
{
 ll i, j, x, y;

 ll table[n+1][m];
 
 for (i=0; i<m; i++)
  table[0][i] = 1;

 for (i = 1; i < n+1; i++)
 {
  for (j = 0; j < m; j++)
  {
  
   x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
   y = (j >= 1)? table[i][j-1]: 0;
   table[i][j] = x + y;
  }
 }
 return table[n][m-1];
}


int main()
{
 ll a[] = {1,5,10,25,50};
 ll m = 5;
 ll n;
 
 while(cin>>n){
  ll ans;
  
  ans = count(a,m,n);
  
  if(ans>1){
   cout<<"There are "<<ans<<" ways to produce "<<n<<" cents change."<<'\n';
  }
  else cout<<"There is only "<<ans<<" way to produce "<<n<<" cents change."<<'\n';
 }
 return 0;
}

UVa 11137

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll a[21];
void precal(){

    for(int i=0; i< 21 ;i++) a[i]= ( (i+1) * (i+1) * (i+1) );

}

ll count( ll S[], ll m, ll n )
{
 ll i, j, x, y;
 ll table[n+1][m];

 for (i=0; i<m; i++)
  table[0][i] = 1;
 for (i = 1; i < n+1; i++)
 {
  for (j = 0; j < m; j++)
  {
   x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
   y = (j >= 1)? table[i][j-1]: 0;
   table[i][j] = x + y;
  }
 }
 return table[n][m-1];
}



int main(){

 precal();

//cout<<a[20];
 ll n,ans;

    while(cin >> n){

        ans = count(a,21,n);
        cout<< ans << '\n';
    }


 return 0;
}

UVa 674

#include<bits/stdc++.h>
#include<iomanip>
#define ll long long

using namespace std;


ll count( ll S[], ll m, ll n )
{
 ll i, j, x, y;

 ll table[n+1][m];
 
 for (i=0; i<m; i++)
  table[0][i] = 1;

 for (i = 1; i < n+1; i++)
 {
  for (j = 0; j < m; j++)
  {
  
   x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
   y = (j >= 1)? table[i][j-1]: 0;
   table[i][j] = x + y;
  }
 }
 return table[n][m-1];
}


int main()
{
 ll a[] = {1,5,10,25,50};
 ll m = 5;
 ll n;
 
 while(cin>>n){
  ll ans;
  
  ans = count(a,m,n);
  
  cout<<ans<<'\n';
 }
 return 0;
}

UVa 10130

#include<bits/stdc++.h>

using namespace std;

int knap(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
 
   return K[n][W];
}

int main(){
 
 int t,n,sum;
 int p[1000+1],w[1000+1];
 int gn,g;
 
  cin>>t;
  while(t--){
   
   sum=0;
   cin>>n;
   for(int i=0; i<n; i++){
    
    cin>>p[i];
    cin>>w[i];
   }
   
   cin>>gn;
   for(int j=0; j<gn; j++){
    cin>>g;
    sum+=knap(g,w,p,n);
   }
   
   cout<<sum<<'\n';
  }
 
 
 return 0;
}

UVa 562

#include<bits/stdc++.h>

using namespace std;

int knap(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
 
   return K[n][W];
}

int main(){
 
 int t,n,w,d,ans,sum;
 
 while(cin>>t){
  
  while(t--){
   
   sum=0;
   cin>>n;
   int wt[100+1],val[100+1];
   memset(wt,0,101);
   memset(val,0,101);
   
   for(int i=0; i<n; i++){
    cin>>wt[i];
    val[i]=wt[i];
    sum+=wt[i];
   }
  
   w = sum/2;
   d = knap(w,wt,val,n);
   ans=sum - 2*d;
   cout<<ans<<'\n';
   
  }
 }
 
 return 0;
}

UVa 10664

#include<bits/stdc++.h>

using namespace std;

int knap(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
 
   return K[n][W];
}


int main(){

 string n;
 int m,sum,d,w,ans;
 int wt[21],val[21];
 
  cin>>m;
  getchar();
  while(m--){
   
   
   getline(cin,n);
   int num;
   istringstream str(n);
   
   int i=0; sum=0;
   while(str >> num){
    sum+=num;
    wt[i]=val[i]=num;
    i++;
    
   }
   
  
   
   if(sum%2==1){
    cout<<"NO"<<'\n';
   }
   else {
    
    w= sum / 2;
    d= knap(w,wt,val,i);
    
    if(d==w) cout<<"YES"<<'\n';
    else cout<<"NO"<<'\n';

   }
   
   }

 return 0;
}