Educational Codeforces Round 114 (Rated for Div. 2) D The Strongest Build（map+vector)

Educational Codeforces Round 114 (Rated for Div. 2) D The Strongest Build（map+vector)

题目大意：
给你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;
}