CF1574D. The Strongest Build 2000 —— 优先队列维护bfs + map*

CF1574D. The Strongest Build 2000 —— 优先队列维护bfs + map*

D

​​​​​​​不要忘记line65 v = now; 也可以不用，把之后的v都换成now即可​​​​​​​

题意：

给你n个数组，每个数组中取一个数字，要求输出最后和最大的取法。

给出m个排序，这m种排序不能取

思路：

暴搜

1.把这m种排序分别映射到map： map<vector<int>, bool> mp, use; mp[i] = 1表示这种取法不能用, use[i] = 1表示这种取法已经被遍历过。

2.v[i]表示当前第i组中取的数的index-1（从0开始）

3.priority_queue<pair<int, vector<int> > >q; first存储当前方案的sum，即按sum从大到小排列，

second存储当前的方案中每个数组中取的是哪个数 即v[i]

首先把每个数组中最大的数加入优先队列，判断是否是m，若不是则输出之，否则枚举把每个数前移动一位，即v[i]-1，不要忘记复原。

// Decline is inevitable,
// Romance will last forever.
#include <bits/stdc++.h>
using namespace std;
#define mst(a, x) memset(a, x, sizeof(a))
#define INF 0x3f3f3f3f
//#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ll  long long
//#define int  long long
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
const int maxn = 2e4;
const int maxm = 1e3 + 10;
const int P = 1e9+7;//998244353;
int n, m;
vector<int> g[15];
int pos[15];
vector<int> v, now;
priority_queue<pair<int, vector<int> > >q;
map<vector<int>, bool> mp, use;
void solve() {cin >> n;int sum = 0;for(int i = 1;i <= n; i++) {int x;cin >> x;for(int j = 1; j <= x; j++) {int tp;cin >> tp;g[i].push_back(tp);}pos[i] = x - 1;sum += g[i][x-1];}for(int i = 1; i <= n; i++) {now.push_back(pos[i]);}q.push({sum, now});int m;cin >> m;for(int i = 1; i <= m; i++) {int tp;v.clear();for(int j = 1; j <= n; j++) {cin >> tp;v.push_back(tp - 1);}mp[v] = 1;}use[now] = 1;while(!q.empty()) {auto tp = q.top();q.pop();now = tp.second;if(!mp[now]) {for(auto i : now) {cout << i + 1 << ' ';}cout << endl;return;}v = now;sum = tp.first;int sum2 = sum;for(int i = 0; i < n; i++) {if(v[i] > 0) {sum2 -= g[i+1][v[i]];v[i]--;sum2 += g[i+1][v[i]];if(!use[v]) {use[v] = 1;q.push({sum2, v});}v[i]++;sum2 = sum;}}}
}
signed main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int T; scanf("%d", &T); while(T--)
//    int T; cin >> T; while(T--)solve();return 0;
}