題意：給定多種郵票的組合，郵票最多只能用S張，這些郵票能組成許多不同面額，問最大連續(xù)面額的長度是多少，如果有多個組合輸出組合中郵票數(shù)量最少的，如果仍有長度一致的，輸出郵票從大到小排序后字典序最大的那個組合。

   思路:d(i)表示面額為i的至少需要多少張郵票才能組成，轉(zhuǎn)移方程d(i) = min(d(k) + d(i - k))，1 <= k < i.

   注意：郵票數(shù)量不能超過S張，連續(xù)是指從1~max，也就是說連續(xù)必須以1作為開頭，否則就算后面能組成更長的連續(xù)也不算。

AC代碼：

#include<cstdio>#include<algorithm>#include<cstring>#include<utility>#include<string>#include<iostream>#include<map>#include<set>#include<vector>#include<queue>#include<stack>using namespace std;#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int> const int maxn = 1000 + 5;int d[15][maxn], len[15];vector<int>s[15];int solve(int S, int k) { //第k種郵票組合 	int n = s[k].size();	//初始化邊界	d[k][0] = 0;	for(int i = 0; i < n; ++i) d[k][ s[k][i] ] = 1;	int up = s[k][n-1] * S;	for(int i = 1; i <= up; ++i) {		if(d[k][i] != -1) continue;		d[k][i] = inf;		for(int j = 1; j < i/2 + 1; ++j) {			if(d[k][i] == -1 || d[k][i-j] == -1) continue;			d[k][i] = min(d[k][i], d[k][j] + d[k][i - j]); //inf + inf不會溢出 			if(d[k][i] > S) d[k][i] = inf;  //防止溢出 		}		}	int ans = 0, cnt = 0;	for(int i = 1; i <= up; ++i) {		if(d[k][i] > S) break;		ans++;	}	return ans;}int main() {	int S, N, n, x;	while(scanf("%d", &S) == 1 && S) {		scanf("%d", &N);		for(int i = 0; i < N; ++i) s[i].clear();		for(int i = 0; i < N; ++i) {			scanf("%d", &n);			for(int j = 0; j < n; ++j) {				scanf("%d", &x);				s[i].push_back(x);			}		}		memset(d, -1, sizeof(d));		int ans = 0;		for(int i = 0; i < N; ++i) {			len[i] = solve(S, i);			ans = max(ans, len[i]);		}		int cur, k, l = inf;		for(int i = 0; i < N; ++i) {			if(len[i] == ans && l > s[i].size()) {				cur = i;				l = s[i].size();			}		}		for(int i = 0; i < N; ++i) {			if(i == cur) continue;			if(len[i] == ans && s[i].size() == l) { //長度相同且集合元素一樣多 				for(int j = l - 1; j >= 0; --j) {					if(s[cur][j] < s[i][j]) break;					else if(s[cur][j] > s[i][j]) {						cur = i;						break;					}				}			}		}		PRintf("max coverage =%4d :", ans);		for(int i = 0; i < s[cur].size(); ++i) printf("%3d", s[cur][i]);		printf("/n");	}	return 0;}