D. The Strongest Build(Edu Div. 2#114)【优先队列搜索】

D. The Strongest Build(Edu Div. 2#114)【优先队列搜索】

D. The Strongest Build(Edu Div. 2#114)【优先队列搜索】

题目

传送门（逐渐懒惰）

思路

只有十个槽，所以大胆一点，存十个槽的状态，从所有槽都是最后一个开始向下宽搜（因为有序递增，所以都选最后一个是最优解），优先队列以当前这个状态的能力和为优先级。简单的说就是宽搜板子，，，就是赛场上傻掉了居然想直接用longlong存状态（不知道为什么以为每个槽也只有10个深度）

代码

#include <bits/stdc++.h>
#define pb push_backusing namespace std;
typedef long long ll;const int N = 20;
int n;struct node
{vector<int> vec;ll val;node(){ val = 0; }node(int n) { val = 0, size(n); }bool operator < (const node& obj) const{return val < obj.val;}
};map<vector<int>, int> mp; //是否被禁止使用
map<vector<int>, int> vis; //是否已访问
vector<vector<int> > c; //即第i个槽第j个数的权值
priority_queue<node> que;void cal(node& now) //计算当前这个状态的能力和，预先算出来节省计算时间
{now.val = 0;for(int i = 1; i <= n; i++){now.val += (ll)c[i][now.vec[i]];}
}void print(node now) //输出
{for(int i = 1; i <= n; i++){printf("%d ", now.vec[i]);}printf("n");
}int main()
{scanf("%d", &n);node s(n + 1);c.resize(n + 1);for(int i = 1, num; i <= n; i++){scanf("%d", &num);s.vec[i] = num;c[i].resize(num + 1);for(int j = 1; j <= num; j++){scanf("%d", &c[i][j]);}}node now(n + 1);int m;scanf("%d", &m);for(int i = 0; i < m; i++){for(int j = 1; j <= n; j++){scanf("%d", &(now.vec[j]));}mp[now.vec] = 1; //标记被禁止的状态}cal(s);que.push(s);vis[s.vec] = 1;while(!pty()){node now = p();que.pop();if(!mp[now.vec]) //第一个被搜索到的未被禁止的状态，即最优{print(now);break;}for(int i = 1; i <= n; i++){if(now.vec[i] <= 1) //如果是1，不能再减continue;ll val = now.val;now.vec[i]--;cal(now); //计算新状态的能力和if(!vis[now.vec]) //防止重复插入{que.push(now);vis[now.vec] = 1;}now.val = val; //还原当前状态now.vec[i]++;}}return 0;
}