SRM 406: FoldThePaper
(問題概要)
数値がグリッド上に書かれた紙を折りたたんで行って重なった数値の合計を最大化する。
(解法)
縦と横を独立に考えることができる。
縦横は各全探索
#include <algorithm> #include <cstdio> #define REP(i,n) for(int i=0; i<(int)(n); i++) #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std; class FoldThePaper { public: int getValue(vector <string> paper); }; void dfs(vector<int> v, set<int> &s){ REP(i,v.size()) s.insert(v[i]); REP(i,v.size() - 1){ vector<int> next; int idx1 = i; int idx2 = i + 1; while(idx1 >= 0 || idx2 < (int)v.size()){ const int aa = idx1 >= 0 ? v[idx1] : 0; const int bb = idx2 < (int)v.size() ? v[idx2] : 0; next.push_back(aa + bb); idx1--; idx2++; } reverse(next.begin(), next.end()); dfs(next, s); } } vector<int> cand(const int n){ vector<int> tmp; set<int> s; REP(i,n) tmp.push_back(1 << i); dfs(tmp, s); return vector<int>(s.begin(), s.end()); } vector<vector<int> > parse(const vector<string> &s){ const int h = s.size(); vector<vector<int> > ret(h); REP(i,h){ stringstream ss(s[i]); int p; while(ss >> p) ret[i].push_back(p); } return ret; } int FoldThePaper::getValue(vector <string> paper){ const vector<vector<int> > p = parse(paper); const int h = p.size(); const int w = p[0].size(); const vector<int> ch = cand(h); const vector<int> cw = cand(w); int ans = -100000000; REP(i,ch.size()){ const int mask = ch[i]; vector<int> sum(w); REP(j,h) if(mask & (1 << j)) REP(k,w) sum[k] += p[j][k]; REP(j,cw.size()){ int s = 0; const int mask2 = cw[j]; REP(k,w) if(mask2 & (1 << k)) s += sum[k]; ans = max(ans, s); } } return ans; }