原题

LRJ入门经典-0905邮票和信封305

难度级别：B； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B

试题描述

假定一张信封最多贴5张邮票，如果只能贴1分和3分的邮票，可以组成面值1-13以及15，但不能组成面值14。我们说：对于邮票组合{1,3}以及数量上限S=5，最大连续邮资为13。

输入S和若干邮票组合，选出最大连续邮资最大的一个组合。如果有多种并列，保证选出的组合中邮票张数最多。如果还有并列，保证最大的邮票面值尽可能小

输入

输入第一行包含一个正整数S(S<=10)，表示邮票数量上限

第二行为一个正整数N（N<=10）

以下N行，每行代表一个邮票集合，第一个数表示集合中邮票的数量，后面从小到大依次表示每张邮票的面值（邮票面值不超过100）

输出

输出包括两行，第一行为最大连续邮资，第二行依次输出该连续邮资对应的邮票组合（多解时按照题目描述的要求输出最恰当的组合）

输入示例

5

2

4 1 4 12 21

4 1 5 12 28

输出示例

71

1 4 12 21

分析

 

代码

#include
     
      #include
      
       #include
       
        using namespace std;struct P{    int s,x[110];}a[11];int dp[11][11000];inline int minn(int xx,int yy){    for(int i=1;i
        
         >n>>m;    for(int i=1;i<=m;i++)    {        cin>>a[i].s;        for(int j=1;j<=a[i].s;j++)        {            cin>>a[i].x[j];            sum+=a[i].x[j]*n;        }    }    memset(dp,9999,sizeof(dp));    for(int i=1;i<=m;i++)    {        if(a[i].x[1]!=1)        {            dp[i][0]=0;            continue;        }        for(int j=1;j<=a[i].s;j++) dp[i][a[i].x[j]]=1;        for(int j=1;j<=1000;j++)        {            if(dp[i][j]==1)            {                if(dp[i][j]>n)                {                    dp[i][0]=j-1;                    break;                }                continue;            }            dp[i][j]=min(dp[i][j],minn(i,j));            if(dp[i][j]>n)            {                dp[i][0]=j-1;                break;            }        }    }    int ii=-1,min_dp=-1,min_s=0,min_o=99999999;    for(int i=1;i<=m;i++)    {        if(dp[i][0]>min_dp) min_dp=dp[i][0],min_s=a[i].s,min_o=a[i].x[a[i].s],ii=i;        if(dp[i][0]==min_dp)        {            if(a[i].s>min_s) min_dp=dp[i][0],min_s=a[i].s,min_o=a[i].x[a[i].s],ii=i;            if(a[i].s==min_s)                if(a[i].x[a[i].s]