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