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;
}

这篇关于Educational Codeforces Round 114 (Rated for Div. 2) D The Strongest Build（map+vector)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！