SRM 532 div1 easy: DengklekMakingChains
解法
3 つ連続になっているものを全部並べて, あと左側と右側にプラス要素があったら添える, ということをやれば良いだけです。
真ん中 only に値があるものは, これだと全く無視されますが, 他になんの値もない場合などは真ん中 only に値があるものが答えになることもあるのに注意です(サンプルにあるので引っかからないような気がしますが)。
class DengklekMakingChains { public: int maxBeauty(vector <string> chains) { int ans = 0, sum = 0; int onlyLeft = 0, onlyRight = 0; vector<pii> d; for (string s : chains) { int flag = 0; if (s[0] != '.') flag |= 1; if (s[1] != '.') flag |= 2; if (s[2] != '.') flag |= 4; if (flag == 1) onlyRight = max(onlyRight, s[0]-'0'); if (flag == 2) ans = max(ans, s[1]-'0'); if (flag == 3) onlyRight = max(onlyRight, s[0]-'0' + s[1]-'0'); if (flag == 4) onlyLeft = max(onlyLeft, s[2]-'0'); if (flag == 5) d.emplace_back(s[0]-'0', s[2]-'0'); if (flag == 6) onlyLeft = max(onlyLeft, s[1]-'0' + s[2]-'0'); if (flag == 7) { for (int i = 0; i < 3; i++) { sum += s[i]-'0'; } } } int left = 0, right = 0; for (pii p : d) { left = max(left, p.second); right = max(right, p.first); } ans = max(ans, onlyLeft+sum+onlyRight); ans = max(ans, left+sum+onlyRight); ans = max(ans, onlyLeft+sum+right); int n = d.size(); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (i==j) continue; ans = max(ans, d[i].second+sum+d[j].first); } return ans; } };