View Code of Problem 611

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int dp[1010];
int main()
{
    int m,n;
    while(~scanf("%d%d",&m,&n))
    {
        int big[24];
        for(int i = 0; i<1010; i++)
        {
            dp[i] = 99999;
        }
        memset(big,0,sizeof(big));
        for(int i = 0; i<n; i++)
        {
            int a,b;
            scanf("%d%d",&b,&a);
            big[b]+=a;
        }
        dp[0] = 0;
        for(int i = 1; i<=23; i++)
            for(int j = 0; j<big[i]; j++)
                for(int z = 1009; z>=0; z--)
                {
                    dp[z] = min(dp[z],dp[z-i]+1);
                }
        if(dp[m]==99999)
            printf("Naivete\n");
        else
            printf("%d\n",dp[m]);
    }
    return 0;
}

Double click to view unformatted code.


Back to problem 611