ABC167 C - Skill Up
問題はこちら atcoder.jp
方針
購入する参考書の組み合わせが高々 通りしかないところを見るに,全探索で解くのが本命です。
今回は「bit全探索」を用いていますが,この手法を使った経験がなかったのでたどたどしいコードになっています。
コード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) int n,m,x; vector<int> c; vector<vector<int>> a; bool judge(int bit); int cost(int bit); int main(){ cin>>n>>m>>x; c.resize(n); a.resize(n); REP(i,n){ cin>>c[i]; a[i].resize(m); REP(j,m){ cin>>a[i][j]; } } int min_=0; // 参考書の組み合わせ分(2^12回)のループ for(int bit=0; bit<(1<<n); bit++){ if(judge(bit)){ if(min_==0){ min_=cost(bit); }else{ min_=min(min_,cost(bit)); } } } cout<<(min_==0 ? -1 : min_)<<endl; } bool judge(int bit){ vector<int> und(n); // 理解度 REP(i,n){ if(bit&(1<<i)){ REP(j,m){ und[j]+=a[i][j]; } } } REP(i,m){ if(und[i]<x){ // 理解度がXに達していない問題があればfalse return false; } } return true; } int cost(int bit){ int sum=0; REP(i,n){ if(bit&(1<<i)){ sum+=c[i]; } } return sum; }