【DP 训练】Stamps and Envelope Size, ACM/ICPC World Finals 1995, UVa242
题意:信封上最多贴S张邮票。有N个邮票集合,每个集合有不同的面值。问哪个集合的最大连续邮资最大,输出最大连续邮资和集合元素。最大连续邮资是用S张以内邮票面值凑1,2,3...到n+1凑不出来了,最大连续邮资就是n。如果不止一个集合结果相同,输出集合元素少的,如果仍相同,输出最大面值小的。
#include<bits/stdc++.h>
using namespace std;
#define maxn 20
int s,n;
int stamp[maxn];
int ans[maxn];
int dp[1100];
int main(void)
{
while(scanf("%d",&s)&&s)
{
int size = 1000,maxv = 1000,bestans = 0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",stamp);
for(int j=1;j<=*stamp;j++)
scanf("%d",&stamp[j]);
memset(dp,0x3f,sizeof(dp));
dp[0] = 0;int tans = 0;
for(int j=1;j<1100;j++)
{
for(int k=1;k<=*stamp&&j>=stamp[k];++k)
dp[j] = min(dp[j],dp[j-stam