这题紫薯上翻译错了
应该是：如果有多个并列，输出邮票种类最少的那个，如果还有并列，输出最大面值最小的那个
坑了我一个下午
dp[p][q]==1表示可以用不超过q张组成面额p
结合记忆化，p从1开始枚举，一直枚举找到dp[p][q]=0的时候就可以了
这题应该归类成一种背包吧
注意dp初始化的时候应该初始化为-1（我就因为粗心，tle好久）
最后输出的时候比较恶心
最终的修改后的代码
实验证明，先读入所有数据后再处理比边读数据边处理要快
/*
* Author: Bingo
* Created Time: 2015/3/4 13:54:40
* File Name: uva242.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
using namespace std;
const int maxint = ;
int S,T,n;
int map[][];
int dp[][];
//int ans[20][20];
int ans,ans_num,ans_max,ans_case;
int fun(int p,int q,int c){
if (dp[p][q]!=-) return dp[p][q];
else if (p==){
dp[p][q]=;
return ;
}else if (q==) {
dp[p][q]=;
return ;
}else {
for (int i=;i<=map[c][];i++) {
if (p>=map[c][i]&&fun(p-map[c][i],q-,c)){
dp[p][q]=;
return ;
}
}
}
dp[p][q]=;
return ;
}
int cmp(int a,int b){//比较最大连续邮资相同的集合
if(map[a][]<map[b][])return a;
if(map[b][]<map[a][])return b;
for(int i=map[a][];i>;i--){
if(map[a][i]<map[b][i])return a;
if(map[b][i]<map[a][i])return b;
}
return a;
}
int main(){
while (cin>>S&&S){
cin>>T;
int mycase=;
ans=;ans_num=maxint;ans_max=maxint;
while (T--){
cin>>n;
mycase++;
memset(dp,-,sizeof(dp));
map[mycase][]=n;
for (int i=;i<=n;i++) {
cin>>map[mycase][i];
}
int p;
for (p=;;p++) {
if (fun(p,S,mycase)==) break;
}
int t=p-;
if (t>ans){
ans=t;
ans_case=mycase;
}else if (t==ans){
ans_case=cmp(mycase,ans_case);
}
}
printf("max coverage =%4d :", ans);
for(int i=;i<=map[ans_case][];i++){
printf("%3d",map[ans_case][i]);
}
printf("\n");
}
return ;
}