NC20048. [HNOI2006]军机调度
描述
输入描述
一行包含两个正整数n,m。彼此用空格隔开，其中n〈10表示雇佣军的人数，m〈15表示下个月可选的任务数。
接下来的n行中，第i行（对应整个文件的第i+1行）的第一个整数小于等于表示编号为i的雇佣军可以执行的任务数，后面的整数是编号为i的雇佣军可以执行的所有任务的编号，这些整数之间用空格隔开。
最后的m行中，每行有四个整数b、e、p和r，彼此之间用空格隔开，其中第j行（对应整个文件的第n+j+1行）是编号为j的任务的描述：0 < b 〈 32表示该任务的开始日（这一天会被计入任务所需的时间中），0 < e〈32表示该任务的结束日（这一天也会被计入任务所需的时间中），p < 10表示该任务所需人数，0 < r 〈 100000表示该任务的报酬。
输出描述
第一行只有一个整数t,表示最多可获得的总报酬
示例1
输入:
3 5 2 1 4 2 2 4 3 3 4 5 2 20 1 100 1 18 1 200 3 28 1 800 21 30 3 1500 19 21 1 400
输出:
1800
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 488K, 提交时间: 2019-03-16 11:09:43
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int count(int x) {
int ans=0;
while (x) {
ans+=x&1;
x>>=1;
}
return ans;
}
#define maxn 35
int b[maxn],e[maxn],r[maxn],ans,n,m,p[maxn],s[maxn];
bool a[maxn][maxn],is[maxn][maxn];
int dfs(int x,int sum) {
if (sum>ans) ans=sum;
if (x==m+1) return 0;
dfs(x+1,sum);
int tot=0,s[maxn];
for (int i=1;i<=n;i++)
if (a[i][x]) {
bool flag=1;
for (int j=b[x];j<=e[x];j++)
if (is[i][j]) {flag=0;break;}
if (flag) s[++tot]=i;
}
if (tot<p[x]) return 0;
for (int i=1;i<(1<<tot);i++) {
if (count(i)!=p[x]) continue;
for (int j=1;j<=tot;j++) {
if ((1<<(j-1))&i){
int y=s[j];
for (int k=b[x];k<=e[x];k++) is[y][k]=1;
}
}
dfs(x+1,sum+r[x]);
for (int j=1;j<=tot;j++) {
if ((1<<(j-1))&i){
int y=s[j];
for (int k=b[x];k<=e[x];k++) {is[y][k]=0;}
}
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) {
int x;
scanf("%d",&x);
for (int j=1;j<=x;j++) {
int y;
scanf("%d",&y);
a[i][y]=1;
}
}
for (int i=1;i<=m;i++) {
scanf("%d%d%d%d",b+i,e+i,p+i,r+i);
}
dfs(1,0);
printf("%d",ans);
return 0;
}