SRM 532 Div2 Medium DengklekMakingChains

鎖が与えられる.各鎖のリンクは綺麗か汚いかにわかれていて,綺麗さにも1〜9の度合いがある.
今この鎖を任意に繋ぎあわせて,綺麗なリンクが続く部分だけを切り取ろうとする.
切り出した部分の綺麗さの総和が最大となるように切り取り,その値を求めよという問題.

汚いリンクを"."で表す.
まず,'11..'と'..11'を組み合わせて'..1111..'など組み合わせると値を大きくできる.
また全て綺麗な鎖'2222'を組み合わせると'..11222211..'なんてのもできる.
ここで鎖の左から汚いものまでの値と,右から汚いものまでの値,全て綺麗な鎖の値の総和を計算しておけば,それらの組み合わせを全て求めることで鎖を組み合わせる場合の最大の値が求めることができる.
また,組み合わせなくても最大の場合もあるので('.9999999.'みたいな),その値も求めて一番大きい値を返す.

class DengklekMakingChains
{
public:
  int maxBeauty(vector <string> chains)
    {
      int onlyone = 0;
      vector<vector<int> > cs;
      int all = 0;
      int n = chains.size();
      int m = chains[0].size();
      int i, j, k;
      vector<int> tmp;
      tmp.push_back(0);
      tmp.push_back(0);
      cs.push_back(tmp); cs.push_back(tmp);
      for(i = 0; i < n; i++){
        int l =0;
        int r = 0;
        for(j = 0; (j < m) && (chains[i][j] != '.'); j++){
          l += chains[i][j]-'0';
        }
        for(k = m-1; (k >= 0) && (chains[i][k] != '.'); k--){
          r += chains[i][k]-'0';
        }
        // cout << "j=" << j << " k=" << k << endl;
        vector<int> tmp;
        if (j != m) tmp.push_back(l);
        if (k != -1) tmp.push_back(r);
        if (j == m && k == -1) all += l;
        else{
          cs.push_back(tmp);
          // cout << "i=" << i << " (" << tmp[0] << "," << tmp[1] << ")" << endl;
        }
        int count = 0;
        for(j = 0; j < m; j++){
          if (chains[i][j] != '.') count += chains[i][j] - '0';
          else {
            onlyone = max(onlyone, count);
            count = 0;
          }
        }
        onlyone = max(onlyone, count);
      }
      int ret = max(onlyone, all);
      // cout << "all=" << all << endl;
      for(i = 0; i < cs.size(); i++){
        for(j = 0; j < i; j++){
          ret = max(ret, all + cs[i][0] + cs[j][1]);
          ret = max(ret, all + cs[j][0] + cs[i][1]);
        }
      }
      return ret;
    }
};