Poj Solution 1882

http://poj.org/problem?id=1882

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define NMAX 101
#define INF 10000
int anset[NMAX],alen,min;
int m[10020];
int t[NMAX];
int N,S,len;
void solve()
{
    int i,j;
    m[0]=0;
    i=1;
    while(1)
    {
        m[i]=INF;
        
        for(j=0;j<len;j++)
        {
            if(t[j]>i)
                break;
            if(m[i]>m[i-t[j]]+1)
            {
                m[i]=m[i-t[j]]+1;
            }
            
        }
        if(m[i]>S)
            break;
        i++;
    }
    i--;
    if(min<i)
    {
        min=i;
        alen=len;
        memcpy(anset,t,sizeof(t));
    }
    else if(min==i)
    {
        if(alen>len)
        {
            alen=len;
            memcpy(anset,t,sizeof(t));
        }
        else if(alen==len)
        {
            if(anset[alen-1]>t[len-1])
                memcpy(anset,t,sizeof(t));
        }
    }
}    
void output()
{
    int i;
    printf("max coverage = %d :",min);
    for(i=0;i<alen;i++)
        printf(" %d",anset[i]);
    printf("n");
}
int main()
{
#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int i;
    scanf("%d",&S);
    while(S)
    {
        scanf("%d",&N);
        min=-1;
        while(N--)
        {
            scanf("%d",&len);
            for(i=0;i<len;i++)
            {
                scanf("%d",&t[i]);
            }
            solve();
        
        }
        output();
        scanf("%d",&S);
    }
#if debug
    fclose(stdin);
    fclose(stdout);
#endif;
    return 1;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *