/*
http://oj.daimayuan.top/course/5/problem/252
蜗蜗一共有 n天假期,在假期的第 i天摸鱼他会得到 ai的快乐值。
如果蜗蜗每天都摸鱼的话,他会有愧疚感,所以蜗蜗制定了这么个计划:
对于每一天,蜗蜗都有一个列表,如果蜗蜗在列表中的每一天都在摸鱼的话,这一天蜗蜗就不能摸鱼。
现在请问蜗蜗如何摸鱼,使得他能获得的快乐值总和最大?请求出快乐值总和最大是多少。
输入格式
第一行一个整数 n表示天数。
第二行 n个整数 a1,a2,...,an。
接下来 n行,对于第 i行,先读入一个整数 li表示第 i天的列表上有几天。
如果 li=0,也就是列表是空的话,表示第 i天没有限制;
否则,再读入 li个数表示列表上列的分别是第几天,数据保证这 li个数两两不同并且都不等于 i。
输出格式
一行一个整数表示答案。
样例输入
4
1 2 3 4
0
1 1
1 2
2 2 3
样例输出
8
20
2 2 9 5 9 3 1 5 8 2 1 6 7 9 3 2 3 2 4 3
5 2 4 5 11 17
5 1 5 7 9 3
1 2
2 2 13
1 20
6 1 2 3 8 15 20
4 11 12 13 14
4 20 19 18 17
6 1 20 5 15 13 12
1 2
1 3
3 4 7 9
1 5
1 6
2 9 11
2 9 12
2 8 14
2 5 16
1 3
11 1 3 5 7 9 8 11 15 16 17 18
数据范围
对于 100%的数据,保证 2≤n≤20,1≤ai≤100000,0≤li<n。
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 21;
int a[N];
int n; int ans = 0;
int limit[N];
void dfs(int idx, int status) {
if (idx == n) {
for (int i = 0; i < n; i++) {
if (status & (1 << i)) {
//检查
if (limit[i] == 0) continue;
if ( (status & limit[i]) == limit[i]) {
return;
}
}
}
int sum = 0;
for (int i = 0; i < n; i++) {
if (status & (1 << i)) {
sum += a[i];
}
}
ans = max(ans, sum);
return;
}
//当前天数选择
dfs(idx + 1, status | (1 << idx));
//当前天数不选择
dfs(idx + 1, status);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {
int t;
cin >> t;
for (int j = 0; j < t; j++) {
int b; cin >> b;
limit[i] |= 1 << (b - 1);
}
}
dfs(0, 0);
cout << ans << endl;
return 0;
}
标签:11,20,int,li,蜗蜗,摸鱼,252,dp
From: https://www.cnblogs.com/itdef/p/18530181