【Link】:

【Description】



给你n个集合;

每个集合都包含一些不同面额的邮票;

(每种邮票都当做有无限张)

然后给你一封信上最多能贴的邮票张数S;

问你,哪一个集合的邮票;

能够贴出来从1开始的,最大的连续邮票面额

优先输出小的集合,集合大小一样的话,从大到小排序后,字典序小的优先输出;

【Solution】



每个邮票都是一个物品;

假设每个邮票都最多能拿S个;

做一个多重背包即可

这里

设f[i][j]表示前i个邮票,邮票的总面额为j的情况最少需要的邮票张数;

对每个集合都做一个这样的多重背包;

然后根据f[n][]获取每个集合能获得的最大连续面额就好了;

(根据f[n][j]是否小于等于s判断能不能获得这个面额)

最后输出,是按照场宽输出。不然会PE



【NumberOf WA】



2



【Reviw】



背包的变形。

背包可以做很多事情.嗯。。



【Code】

#include <bits/stdc++.h>

using namespace std;

const int NN = 10;

const int S = 10;

const int MAX_SIZE = 1000;

const int INF = 0x3f3f3f3f;

int s,N,num[S+5],f[NN+5][MAX_SIZE+5];

vector <int> v[NN+5];

int get_ans(int idx,int n){

    memset(f,INF,sizeof f);

    f[0][0] = 0;

    for (int i = 0;i <= n-1;i++)

        for (int j = 0;j <= MAX_SIZE;j++)

            if (f[i][j]<INF){

                for (int k = 0;k <= s;k++){

                    int temp = j + k*v[idx][i+1];

                    f[i+1][temp] = min(f[i+1][temp],f[i][j]+k);

                }

            }

    for (int i = 0;i <= MAX_SIZE+1;i++)

        if (f[n][i] > s) return i-1;

    return 520;

}

int cmp(int idx1,int idx2){

    for (int i = num[idx1];i >= 1;i--)

        for (int j = num[idx2];j >= 1;j--)

            if (v[idx1][i]!=v[idx2][j]){

                if (v[idx1][i] < v[idx2][j])

                    return 1;

                else

                    return 0;

            }

    return 1;

}

int main(){

    //freopen("F:\\rush.txt","r",stdin);

    for (int i = 1;i <= 10;i++)

        v[i].resize(11);

    while (~scanf("%d",&s) && s){

        scanf("%d",&N);

        int ma = 0,maxid = 1;

        for (int i = 1;i <= N;i++){

            scanf("%d",&num[i]);

            for (int j = 1;j <= num[i];j++)

                scanf("%d",&v[i][j]);

            int temp1 = get_ans(i,num[i]);

            if (temp1 > ma){

                ma = temp1;

                maxid = i;

            }else if (temp1 == ma){

                if (num[i] < num[maxid]){

                    maxid = i;

                }else if (num[i] == num[maxid]){

                    if (cmp(i,maxid) == 1)

                        maxid = i;

                }

            }

        }

        printf("max coverage =%4d :",ma);

        for (int j = 1;j <= num[maxid];j++)

            printf("%3d",v[maxid][j]);

        puts("");

    }

    return 0;

}