Educational Codeforces Round 114 (Rated for Div. 2) D. The Strongest Build T10 D43
Educational Codeforces Round 114 (Rated for Div. 2)
思路：
最终结果要么是每组数选最大的，要么是每个被banned的组里面其中一个-1形成的选择。所以贪心的取选择。判重的时候可以用 set< vector
参考代码
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define fi first
#define se second
#define ull unsigned long long
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const ll mod=1e9+7;
const int qs=2e5+17;
const int inf = 0x3f3f3f3f;
int T,n,m,cnt;
ll a[qs],b[qs];
vector<ll> v[qs];
vector<ll> ans;
ll Max=0;
set< vector<ll> > st;
void cal(vector<ll> va){
ll sum=0;
for(int i=1;i<=n;++i){
int p=va[i-1];
sum+=v[i][p-1];
}
if(sum>Max){
Max=sum,ans=va;
}
}
int main(){
n=read();
vector<ll> vm;
for(int i=1;i<=n;++i){
T=read();
vm.pb(T);
for(int j=1;j<=T;++j){ ll x;
x=read();
v[i].pb(x);
}
}
m=read();
ll x;
for(int i=1;i<=m;++i){
vector<ll> vc;
for(int j=1;j<=n;++j){
x=read(); vc.pb(x);
}
st.insert(vc);
}
if(!st.count(vm)){ //每组选最大的
cal(vm);
}
else{
for(auto it=st.begin();it!=st.end();++it){
vector<ll> va=*it;
for(int i=1;i<=n;++i){
//每个被banned的组里面选一个-1；
if(va[i-1]<=1) continue;
va[i-1]-=1;
if(!st.count(va)) cal(va);
va[i-1]+=1;
//之后要加回来
}
}
}
for(int i=0;i<n;++i) cout<<ans[i]<<" ";
return 0;
}
/*
*/
/*
#########
############
#############
## ###########
### ###### #####
### ####### ####
### ########## ####
#### ########### ####
##### ########### #####
###### ### ######## #####
##### ### ######## ######
###### ### ########### ######
###### #### ############## ######
####### ##################### #######
####### ##############################
####### ###### ################# #######
####### ###### ###### ######### ######
####### ## ###### ###### ######
####### ###### ##### #####
###### ##### ##### ####
##### #### ##### ###
##### ;### ### #
## #### ####
*/