D. The Strongest Build（bfs+优先队列）

D. The Strongest Build（bfs+优先队列）

题目链接

题意：有n个数组，需要在每个数组中选取一个下标，然后将这些选取的下标的数求和，但是有m个下标序列是被禁止的，在不与这些序列相同的前提下，输出一个求和后数字最大的下标序列。

思路：用map嵌套vector对下标序列进行标记，然后用bfs进行广搜，每次改变最大序列的一个下标，然后压到优先队列中，以数的总和作为优先队列的第一值，然后每次结束后拿出的vector如果在map中没有出现过，则该序列的答案一定是最大值。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
map<vector<int>,int>mp;
map<vector<int>,int>vis;
vector<int>ve[20];
int n,m,k,x;
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&k);for(int j=1;j<=k;j++){scanf("%d",&x);ve[i].push_back(x);}}scanf("%d",&m);vector<int>temp;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){scanf("%d",&x);temp.push_back(x);}mp[temp]=1;temp.clear();}int val=0;for(int i=1;i<=n;i++){temp.push_back(ve[i].size());val+=ve[i][ve[i].size()-1];}priority_queue<pair<int,vector<int> > > q;q.push({val,temp});while(!q.empty()){vector<int> tem&#p().second;int val&#p().first;q.pop();if(!mp.count(tem)){for(int i=1;i<=n;i++){cout<<tem[i-1]<<" ";}cout<<'n';break;}for(int i=1;i<=n;i++){if(tem[i-1]!=1){tem[i-1]--;if(!unt(tem)){vis[tem]=1;q.push({val+ve[i][tem[i-1]-1]-ve[i][tem[i-1]],tem});}tem[i-1]++;}}}
}