uva 11825

本文主要是介绍uva 11825，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

刘书上例题  关于集合的动态规划

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#define maxn 200010
#define INF 0x7fffffff
#define inf 10000000
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
using namespace std;int p[20], f[maxn], s[maxn], n;void init()
{for(int i = 0; i < n; ++ i){p[i] = 1 << i;int m, x;scanf("%d", &m);while(m --){scanf("%d", &x);p[i] |= (1 << x);}}for(int S = 1; S < (1 << n); ++ S){s[S] = 0;for(int i = 0; i < n; ++ i) if(S & (1 << i)) s[S] |= p[i];}
}
int main()
{int ca = 0;while(scanf("%d", &n) == 1 && n){init();int all = (1 << n) - 1;f[0] = 0;for(int i = 1; i < (1 << n); ++ i){f[i] = 0;for(int S = i; S; S = i&(S-1))if(s[S] == all) f[i] = max(f[i], f[i^S]+1);}printf("Case %d: %d\n", ++ ca, f[all]);}return 0;
}

这篇关于uva 11825的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---