DTDOI - Đổi tiền

Tác giả: ll931110

Ngôn ngữ: C++

#include <iostream>
#define MAXN 101
#define MAXV 10000
#define MAXK 1000000000
using namespace std;

int F[MAXV],a[MAXN],n,s;

int main()
{
    int i,j,k,max,res;
    
    //freopen("dtdoi.inp","r",stdin);
    //freopen("dtdoi.out","w",stdout);
    
    scanf("%d%d", &n, &s);
    max = 0;
    for (i = 1; i <= n; i++) 
      {
           scanf("%d", &a[i]);
           if (max < a[i] && a[i] <= s) max = a[i];
      }
    
    for (i = 0; i < MAXV; i++) F[i] = MAXK;
    F[0] = 0;
    
    for (i = 1; i < MAXV; i++)
      for (j = 1; j <= n; j++)
        if (i >= a[j])
          if (F[i] > F[i - a[j]] + 1) F[i] = F[i - a[j]] + 1;
          
    if (s >= MAXV)
    {
          k = ((s - MAXV) / max) + 1;
          s -= k * max;
    }
    else k = 0;
    
    res = MAXK;
    do
    {
        if (res > k + F[s]) res = k + F[s];
        k++;
        s -= max;
    }
    while (s >= 0);
    
    printf("%d", res);
}

Download