ACM (TJU) : 2768


// http://acm.tju.edu.cn/toj/showp2768.html

#include <stdio.h>

int main ()
{
    int c;
    int n;

    scanf ("%d %d", &c, &n);

    int value [12];

    for ( int i = 0; i < n; i++ )
        scanf ("%d", &value [i]);

    int min [1000];

    for ( int i = 0; i < 1000; i++ )
        min [i] = 1002;

    min [0] = 0;

    for ( int i = 1; i <= c; i++ ) {
        for ( int j = 0; j < n; j++ ) {
            if ( value [j] <= i && min [i - value [j]] + 1 < min [i])
                min [i] = min [i - value [j]] + 1;
        }
    }

    printf ("%d\n", min [c]);

    return 0;
}

One thought on “ACM (TJU) : 2768

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s