题目大意:
给你n行数字
每组数字按递增顺序给出
再给你m个禁止的序列
就是你不能按这些序列来选这n行的数字
问你除了禁止序列的顺序外每行选一个数字的最大值
思路:
map+vector
感觉就是考察stl运用吧…
我们可以首先每行都选最后一个数字即最大的数字
然后如果这个是被禁止的
那么我们就遍历所有禁止的数组
枚举每行的前一个数字去选
如果这个枚举的序列是被禁止的那到后面会再过来遍历这个序列
这样就保证了一定会遍历到最优解
怎么看被禁止的话我们就可以用map[vector]去看这个数组是不是被禁止的
剩下的基本是stl运用了吧
时间复杂度应该是1e5*10
每个位置往前枚举一次,最多有10个位置
AC代码:
#include <bits/stdc++.h> using namespace std; map<vector<int>,int>mp; vector<int>h; int main() { ios::sync_with_stdio(false),cin.tie(0); int n; cin>>n; vector<vector<int>>a(n); for(int i=0; i<n; i++) { int c; cin>>c; a[i].resize(c);//开长度为c的数组 for(int j=0; j<c; j++)cin>>a[i][j]; h.push_back(c-1); } int m; cin>>m; for(int i=0; i<m; i++) { vector<int>H; for(int j=0; j<n; j++) { int x; cin>>x; H.push_back(x-1); } mp[H]=1; } int ans=0,cnt=0; if(mp[h]) { for(auto temp:mp) { cnt=0; vector<int>v=temp.first; for(int i=0; i<n; i++) cnt+=a[i][v[i]]; if(cnt<=ans)continue; for(int i=0; i<n; i++) { if(v[i]) { v[i]--; if(!mp[v]) { int tot=cnt+a[i][v[i]]-a[i][v[i]+1]; if(tot>ans) { ans=tot; h=v; } } v[i]++; } } } } for(int i=0; i<n; i++)cout<<h[i]+1<<' '; cout<<endl; return 0; }