博客

WA了一晚上，换了两种dp的写法都不对，郁闷的不行。。结果是大白书翻译错了。。

dp过程很简单，直接上代码吧。

两种dp都能过，第二个效率更高。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;
typedef unsigned long long LLU;

int S, N, n, max_cov, ans_num;
int coin[1010], ans[1010];

/*d[i][j]表示用i个邮票能否组成j的面值*/
//int dp()
//{
//    int d[11][1111]={0};
//    int dd[1111]={0};
//    d[0][0]=1;
//    for(int i=1; i<=S; i++)
//        for(int j=1; j<=1000; j++)
//            for(int k=1; k<=n; k++)
//                if(j>=coin[k] && d[i-1][j-coin[k]])
//                {
//                    d[i][j]=1;
//                    dd[j]=1;
//                    break;
//                }
//    for(int i=1; i<1111; i++)
//        if(!dd[i])
//            return i-1;
//}

/*d[i]表示组成i的面值最少需要多少邮票*/
int dp()
{
    int d[1111];
    for(int i=0; i<1111; i++)
        d[i]=111;
    d[0]=0;
    for(int i=1; i<=n; i++)
        for(int j=coin[i]; j<1111; j++)
            d[j]=min(d[j], d[j-coin[i]]+1);

    for(int i=1; i<1111; i++)
        if(d[i]>S)
            return i-1;
}

int jud()
{
    for(int i=ans_num; i>=1; i--)
    {
        if(coin[i]<ans[i])
            return 1;
        else if(coin[i]>ans[i])
            return 0;
    }
    return 0;
}

void update_ans(int x)
{
    if(x>max_cov)
    {
        max_cov=x;
        ans_num=n;
        memcpy(ans, coin, sizeof(ans));
        return ;
    }
    if(x==max_cov && (n<ans_num || (n==ans_num && jud() )))
    {
        max_cov=x;
        ans_num=n;
        memcpy(ans, coin, sizeof(ans));
    }
}

int main()
{
    while(~scanf("%d", &S) && S)
    {
        max_cov=0;
        ans_num=100;
        int N;
        scanf("%d", &N);
        while(N--)
        {
            scanf("%d", &n);
            if(n>1000)
                while(1);
            for(int i=1; i<=n; i++)
                scanf("%d", &coin[i]);
            sort(coin+1, coin+1+n);
            update_ans(dp());
        }
        printf("max coverage =%4d :", max_cov);
        for(int i=1; i<=ans_num; i++)
            printf("%3d", ans[i]);
        puts("");
    }
    return 0;
}