1 条题解
-
1
#include<iostream> #include<vector> #include<algorithm> using namespace std; int n,m,k,x,ans,a[20]; vector<int> p[15]; struct node { int l,r,p,mn; }w[20]; bool cmp(int x,int y) { return w[x].l==w[y].l?w[x].r<w[y].r:w[x].l<w[y].l; }//按起始结束时间排序 void DFS(int x,int y,int ti) { if(x==n+1)//搜到了一种情况 { int sum=0; for(int i=1;i<=m;i++)//统计答案 if(a[i]==w[i].p) sum+=w[i].mn; ans=max(ans,sum);//更新答案 return; } if(p[x].size()<=y) DFS(x+1,0,1);//这个人搜完了,搜下一个人 //因为vector下标从0~size()-1,所以是<= else { DFS(x,y+1,ti);//不做这个任务 if(w[p[x][y]].l>=ti)//现在闲着的时间和任务时间不冲突 { a[p[x][y]]++;//人数+1 DFS(x,y+1,w[p[x][y]].r+1);//下一个任务 a[p[x][y]]--;//回溯 } } } int main() { cin>>n>>m;//读入 for(int i=1;i<=n;i++) { cin>>k; for(int j=1;j<=k;j++) { cin>>x; p[i].push_back(x); } } for(int i=1;i<=m;i++) cin>>w[i].l>>w[i].r>>w[i].p>>w[i].mn; for(int i=1;i<=n;i++)//排序 sort(p[i].begin(),p[i].end(),cmp); DFS(1,0,1);//搜索(注意从0开始) cout<<ans<<endl; return 0; }
- 1
信息
- ID
- 3471
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者