2013年9月23日 星期一

2013/9/23 UVA 10465 - Homer Simpson

/* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1406 */
#include <iostream>
#include <cstdio>

using namespace std;

bool id[10000]; int dp[10000];

int main()
{
    int m, n, t;
    while( scanf("%d", &m) != EOF )
    {
        scanf("%d %d", &n, &t);

        for(int i = 0; i <= t; i++){ id[i] = false; dp[i] = 0; }


        id[0] = true;

        for(int i = m; i <= t; i++)
        {
            if( id[ i-m ] == true )
                if( dp[i] < dp[ i-m ] + 1 ){ id[i] = true; dp[i] = dp[ i-m ] + 1; }
        }

        for(int i = n; i <= t; i++)
        {
            if( id[ i-n ] == true )
                if( dp[i] < dp[ i-n ] + 1 ){ id[i] = true; dp[i] = dp[ i-n ] + 1; }
        }

        for(int i = t; i >= 0; i--)
        {
            if( id[i] == true )
            {
                printf("%d", dp[i]);
                if( i != t )
                    printf(" %d", t-i);
                printf("\n");
                break;
            }
        }
    }
}

沒有留言:

張貼留言