原题
| 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<iostream>
#include<algorithm>
#include<cstring>
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<yy;i++)
for(int j=i;j<yy;j++)
if(i+j==yy && (dp[xx][i]+dp[xx][j])<dp[xx][yy]) dp[xx][yy]=dp[xx][i]+dp[xx][j];
}
int main()
{
int n,m,sum=0;
cin>>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]<min_s) min_dp=dp[i][0],min_s=a[i].s,min_o=a[i].x[a[i].s],ii=i;
}
}
/*cout<<endl<<endl;
for(int i=1;i<=1000;i++) cout<<dp[1][i]<<" ";
cout<<endl<<endl;
for(int i=1;i<=1000;i++) cout<<dp[2][i]<<" ";
cout<<endl<<endl;*/
cout<<min_dp<<endl;
cout<<a[ii].x[1];
for(int i=2;i<=a[ii].s;i++) cout<<" "<<a[ii].x[i];
return 0;
}
/*
10
2
5 1 7 16 31 88
5 1 15 52 67 99
*/