SRM554Div2
Easy
制約が小さいので全通り試す。
交互に置くので、タワーを建設できるかどうかは、使うブロックの数の差が1以下で判定。
テンプレが長くて減点をくらう。
#include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> //repetition //------------------------------------------ #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) //constant //-------------------------------------------- static const double EPS = 1e-5; static const double PI = acos(-1.0); //clear memory #define CLR(a) memset((a), 0 ,sizeof(a)) //debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; using namespace std; inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;} template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();} typedef long long ll; class TheBrickTowerEasyDivTwo { public: int find(int rc, int rh, int bc, int bh) { int result=0; vector<int> cnt(100000,0); for( int r=0; r<= rc ; r++ ) for( int b=0; b<= bc ; b++ ) { if( abs(r-b) <= 1 ){ cnt[ r*rh+b*bh ]++; } } for( int i=1; i<cnt.size(); ++i) { if( cnt[i] ) { result++; } } return result; } };
Medium
ソートしたら最適解になるのはわかるが、答えが辞書順で最小でないといけない。
入力サイズが最大7なので全通り試しても7!=5040通りなので結局全探索。
辞書順の判定はvectorの比較演算子を使えばOK。
テンプレ減点を防ぐために削るなど。
#include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> //repetition //------------------------------------------ #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) using namespace std; typedef long long ll; class TheBrickTowerMediumDivTwo { public: int calc( const vector<int>& d , const vector<int>& h ){ int ret = 0; REP(i,d.size()-1){ ret += max( h[d[i]] , h[d[i+1]] ); } return ret; } vector <int> find(vector <int> heights) { vector <int> result; map< int , vector< int > > memo; vector<int> v; REP(i,heights.size()) { v.push_back(i); } do{ int k = calc( v, heights ); if( memo.find(k) == memo.end() ) { memo[k] = v; }else { if ( memo[k] > v ){ memo[k] = v; } } }while( next_permutation( v.begin(),v.end() ) ); result = memo.begin()->second; return result; } };
Hardだれか教えて。。