Educational Codeforces Round 114 (Rated for Div. 2) D.The Strongest Buil(暴力)

Educational Codeforces Round 114 (Rated for Div. 2) D.The Strongest Buil(暴力)

1.题目链接：
2.题意：一个人他穿装备，有 n n n个部位可以穿。第 i i i个部位有 c i c_i ci​件装备可以选择，加的属性是 a [ i ] [ c i ] a[i][c_i] a[i][ci​]（每个部位的装备属性按从小到大排列），有 m m m种装备组合是被ban掉不能使用的。现在让你找出最大属性和的装备组合。
3.思路：考虑暴力搜索：
对于第一个样例：

我们可以得到这样一颗搜索树：

首先发现有许多状态是重复的，可以DP或者记忆化搜索，但是这样做并不能让搜索空间缩小的可以接受的范围内。所以得考虑其他性质，我们发现在搜索树上父节点对应得属性和一定大于所有儿子节点（包括儿子的儿子…）的属性，所以我们如果搜过了父亲，就不用去管儿子节点了。这样我们的思路就出来了，在BFS的过程中，只加入父节点被BAN掉的子节点，这样就可以保证在可以接受的范围内找到最合适的答案了。判重的话可以哈希（没试过），我这里用的set（用set还错了好几次）（map也可以）。
4.代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
struct node{int p[10];//乱写的，保证set中不会把两个不同元素判成相同即可bool operator<(const node b)const{for(int i=0;i<10;i++){if(this->p[i]!=b.p[i]) return this->p[i]<b.p[i];}return 0;}
};
int a[17][N];
node b;
set<node> se,ed;
int main()
{int n;scanf("%d",&n);for(int i=0;i<n;i++){int k;scanf("%d",&k);b.p[i]=k;for(int j=1;j<=k;j++) scanf("%d",&a[i][j]);}for(int i=n;i<10;i++) b.p[i]=0;int m;scanf("%d",&m);for(int i=0;i<m;i++){node s;for(int i=0;i<n;i++){int temp;scanf("%d",&temp);s.p[i]=temp;}for(int i=n;i<10;i++) s.p[i]=0;se.insert(s);}queue<node> q;q.push(b);node ans;int ma=0;while(!q.empty()){node t=q.front();q.pop();//记忆化unt(t)!=0) continue;ed.insert(t);//遍历//如果没有被unt(t)==0){int now=0;for(int i=0;i<n;i++){int x=t.p[i];now+=a[i][x];}
//			for(int i=0;i<n;i++) printf("abc%d ",t.p[i]);
//			printf("%dn",now);if(now>ma){ma=now;for(int i=0;i<n;i++) ans.p[i]=t.p[i];}}//被ban了就把儿子加入else{for(int i=0;i<n;i++){if(t.p[i]!=0&&t.p[i]!=1){t.p[i]--;q.push(t);t.p[i]++;}}}}for(int i=0;i<n;i++){printf("%d ",ans.p[i]);}printf("n");
}