UVA - 242 线性DP

      题意：给定多种邮票的组合，邮票最多只能用S张，这些邮票能组成许多不同面额，问最大连续面额的长度是多少，如果有多个组合输出组合中邮票数量最少的，如果仍有长度一致的，输出邮票从大到小排序后字典序最大的那个组合。

   思路:d(i)表示面额为i的至少需要多少张邮票才能组成，转移方程d(i) = min(d(k) + d(i - k))，1 <= k < i.

   注意：邮票数量不能超过S张，连续是指从1~max，也就是说连续必须以1作为开头，否则就算后面能组成更长的连续也不算。

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;}