题意:给定多种邮票的组合,邮票最多只能用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; }